Ruler and Compass
National Olympiad — National round (2015 season)
Submission name: ruler_compass.cpp
Problem summary
Starting with identified points (0,0) and (1,0), construct a newly generated point within Euclidean distance 0.001 of a target. Each operation intersects two lines or circles defined using existing points. The score decreases with the number of intersection calls.
Input
The grader invokes void go(double tarx, double tary). Call define_line(int ida, int idb) or define_circle(int center, int radiusA, int radiusB) twice before each intersect(int &id1, double &x1, double &y1, int &id2, double &x2, double &y2). intersect returns 0, 1 or 2 and assigns fresh point identifiers and coordinates.
Output
Call done(int id) with the identifier of a newly generated point at distance at most 0.001 from the target, then return. Submit ruler_compass.cpp without main().
Constraints
0 ≤ tarx,tary < 10000. Lines require distinct points; circles require positive radius. Coincident objects are invalid. With p intersections, the per-test score is max(0,min(10,10−0.085(p−45))).
Worked example
This is the official example interaction, not standard input/output. Valid construction sequences and fresh identifiers are nonunique; this implementation follows its documented dyadic construction instead.
Input
Grader calls go(1.5, 0.866025404).
Output
The official interaction constructs (2,0), then intersects unit circles centered at (1,0) and (2,0), and calls done on the upper intersection.
Solution analysis
- This implementation gives a valid approximation over the full coordinate domain, with a bounded operation count rather than a maximum-score claim. Construct the midpoint of a horizontal segment using the intersection of two equal-radius circles followed by the intersection of their perpendicular bisector with the x-axis. Ten halvings of [0,1] produce h=1/1024 in 20 intersection calls.
- Double h repeatedly by intersecting the x-axis with the circle centered at the current positive endpoint and passing through the origin. The other intersection is twice that endpoint. After 24 doublings, all powers 2^k h for 0≤k≤24 are available. Round each target coordinate to the nearest integer multiple of h. Construct that multiple by adding the powers corresponding to its set bits, or subtracting the powers of 2^24−n from 2^24 h. An addition or subtraction is one circle–axis intersection; select the right or left intersection by its returned coordinate.
- To place the final ordinate, intersect the unit circle centered at (x,0) with the axis, obtaining (x−1,0) and (x+1,0). Their equal-radius circle intersections determine the vertical through x. Intersect it with the circle centered at (x,0) whose radius is the constructed ordinate, and select the upper point. A zero rounded ordinate needs no placement. For the official target, the grid construction uses x=1.5 and y=887/1024=0.8662109375; its error is about 0.000186. Its interaction differs from the shorter official example.
- Each integer n fits in 24 bits. If n has at most 13 set bits, direct addition takes at most 12 calls. Otherwise popcount(2^24−n)≤25−popcount(n)≤11, so subtraction takes at most 11 calls. The source selects subtraction conservatively using this bound. The total is at most 20+24+12+12+3=71 intersections, corresponding to at least 7.79 of 10 points per test under the published formula in exact geometry. This is a construction bound, not an online-judge acceptance or maximum-score claim.
Why it works
Midpoint construction follows from equal distances to the endpoints. Circle–axis intersections at center c and radius r have coordinates c−r and c+r, proving every doubling and binary sum/subtraction. Thus the constructed coordinates are the nearest grid multiples of h. Each coordinate error is at most h/2, so the Euclidean error is at most sqrt(2)/2048 < 0.001. The perpendicular bisector used for placement is exactly the vertical through the abscissa, and selecting the upper intersection supplies the nonnegative ordinate. Every radius is positive, every line has distinct defining points, and each intersect receives exactly two newly defined objects. Zero coordinates use a fresh origin generated during doubling.
Watch out. Keep the actual grader API and omit main(). Do not assume intersection ordering or invent identifiers. Avoid zero-radius circles for a zero ordinate. The distance tolerance is Euclidean, so approximating each coordinate to error 0.001 is insufficient.
Commented C++17 solution
Link this source with the supplied contestant grader; the test suite uses a clearly labelled independent local geometry mock. The program preserves the official function signatures.
#include<array>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
void define_line(int ida,int idb);
void define_circle(int center,int radiusA,int radiusB);
int intersect(int&id1,double&x1,double&y1,int&id2,double&x2,double&y2);
void done(int id);
namespace{
struct Point{
int id;
double x;
double y;
};
vector<Point>crossing(){
Point a{},b{};
int count=intersect(a.id,a.x,a.y,b.id,b.x,b.y);
vector<Point>result;
if(count>=1){
result.push_back(a);
}
if(count==2){
result.push_back(b);
}
return result;
}
Point horizontalExtreme(int center,int radiusA,int radiusB,bool right){
define_line(0,1);
define_circle(center,radiusA,radiusB);
vector<Point>points=crossing();
if(points.size()==1){
return points[0];
}
return (points[0].x>points[1].x)==right?points[0]:points[1];
}
Point midpoint(int left,int right){
define_circle(left,left,right);
define_circle(right,left,right);
vector<Point>points=crossing();
define_line(points[0].id,points[1].id);
define_line(0,1);
return crossing()[0];
}
} // namespace
void go(double tarx,double tary){
// A grid spacing of 1/1024 gives Euclidean rounding error below 0.001.
Point unit{1,1.0,0.0};
for(int i=0;i<10;++i){
unit=midpoint(0,unit.id);
}
array<Point,25>power;
power[0]=unit;
Point freshZero{};
for(int bit=1;bit<=24;++bit){
define_line(0,1);
define_circle(power[bit-1].id,0,power[bit-1].id);
vector<Point>points=crossing();
if(points[0].x>points[1].x){
swap(points[0],points[1]);
}
freshZero=points[0];
power[bit]=points[1];
}
auto coordinate=[&](double target){
int number=static_cast<int>(llround(target*1024.0));
if(number==0){
return freshZero;
}
int ones=0;
for(int bit=0;bit<24;++bit){
if((number>>bit)&1){
++ones;
}
}
// Use either its set bits, or subtract the missing bits from 2^24.
bool subtract=25-ones<ones-1;
Point value=subtract?power[24]:freshZero;
if(subtract){
int missing=(1<<24)-number;
for(int bit=0;bit<24;++bit){
if((missing>>bit)&1){
value=horizontalExtreme(value.id,0,power[bit].id,false);
}
}
}
else{
bool started=false;
for(int bit=0;bit<24;++bit){
if((number>>bit)&1){
value=started?horizontalExtreme(value.id,0,power[bit].id,true):power[bit];
started=true;
}
}
}
return value;
};
Point x=coordinate(tarx);
Point y=coordinate(tary);
if(llround(tary*1024.0)==0){
done(x.id);
return;
}
// The perpendicular bisector of (x-1,0),(x+1,0) is the vertical through x.
define_line(0,1);
define_circle(x.id,0,1);
vector<Point>ends=crossing();
define_circle(ends[0].id,ends[0].id,ends[1].id);
define_circle(ends[1].id,ends[0].id,ends[1].id);
vector<Point>vertical=crossing();
define_line(vertical[0].id,vertical[1].id);
define_circle(x.id,0,y.id);
vector<Point>answer=crossing();
Point result=answer[0];
for(Point point:answer){
if(point.y>result.y){
result=point;
}
}
done(result.id);
}