Under construction

Still being built. Things may change

Drawing Lines

Time limit1sMemory limit2048 MB

Summary
Reproduce a hidden segment with endpoints in [-10000, 10000] and length at least 100, using interactive guesses scored by endpoint distance within 25000 tries.
Level

Medium7 of 10

Topics
Geometry, Binary search, Math
Solved
No attempts yet

Statement

This is an interactive problem.

The jury has an image of a straight line segment with endpoints (X1,Y1)(X_1, Y_1) and (X2,Y2)(X_2, Y_2). The coordinates satisfy the following constraints:

  • X1,Y1,X2,Y2∈[−10000,10000]X_1, Y_1, X_2, Y_2 \in [-10000, 10000]
  • The length of the segment is at least 100100.

Your task is to produce the same image.

You can create several images of the same kind: images of a straight line segment with endpoints (x1,y1)(x_1, y_1) and (x2,y2)(x_2, y_2). After you create an image, you get its similarity sim\mathrm{sim} to the jury's image by the following formulas.

dst(a1,b1,a2,b2)=(a1−a2)2+(b1−b2)2\mathrm{dst}(a_1, b_1, a_2, b_2) = \sqrt{(a_1 - a_2)^2 + (b_1 - b_2)^2}

s=min⁡(dst(x1,y1,X1,Y1)+dst(x2,y2,X2,Y2),dst(x1,y1,X2,Y2)+dst(x2,y2,X1,Y1))s = \min\left(\mathrm{dst}(x_1, y_1, X_1, Y_1) + \mathrm{dst}(x_2, y_2, X_2, Y_2), \mathrm{dst}(x_1, y_1, X_2, Y_2) + \mathrm{dst}(x_2, y_2, X_1, Y_1)\right)

sim=max⁡(0,40000−s40000)\mathrm{sim} = \max\left(0, \frac{40000 - s}{40000}\right)

The goal is to make an image with 100%100\% similarity using no more than 2500025000 tries.

Examples1

  1. Example 1

    Input
    
    29.4
    
    94.9
    
    99.7
    
    99.9
    
    99.7
    
    99.9
    
    100.0
    
    Expected output
    -10000 -10000 10000 10000
    
    0 -1000 0 1000
    
    100 -10 -100 10
    
    -70 0 70 0
    
    -50 0 -50 1
    
    50 0 -50 1
    
    50 0 -50 0