Recover Randomly Sampled Circles
Autumn Tournament (2024)
Submission name: circle.cpp
Problem summary
There are k unknown circles. Each telescope call returns a uniformly random point from a uniformly random circle. Recover all centers and radii using few calls. Implement void solve(int k), include circle.h, call std::pair<double,double> sample_star(), and report each circle exactly once with void answer(double center_x,double center_y,double radius). Do not provide a judge main or standard input/output. The listing includes a separate LOCAL simulator, not the actual interactive protocol.
Source clarification. Read official A2_circle.zip solution_presample_1000.cpp, solution_incremental.cpp and grader protocol; never executed downloaded code. Independent RANSAC/refinement with explicitly disclosed probabilistic and numerical limitations.
Input
Judge: k is passed to solve; points arrive through sample_star(). LOCAL: k, an unsigned seed and radial noise bound, followed by k lines center_x center_y radius. The simulator uses uniform circle choices and angles with optional bounded radial noise.
Output
Judge: exactly k answer calls, in any order; each center coordinate and radius must have absolute error≤0.001. LOCAL: Correct after matching all recovered parameters to distinct true circles. Sample counts go to standard error.
Constraints
2≤k≤20; at most100000 sample_star calls; absolute center coordinates and positive radii≤500000; distinct centers more than100 apart. Each point is within10^−4 of its true circumference. Any parameter error>0.001 gives zero; otherwise score fraction0.3+0.7·sqrt(500/max(Q,500)). Supports all stated k, but no guaranteed success on every random stream or maximum score is claimed.
Worked example
LOCAL example using the circles from the original communication illustration. Its independent simulator checks all three parameters, regardless of reporting order.
Input
2 17 0 100 200 50 -150 -300 75
Output
Correct
Solution analysis
- Three non-collinear points determine a circle, but sample membership is unknown. Use random-sample consensus (RANSAC): collect500 stars and choose triples from unexplained points. With r comparably represented remaining circles, a random triple belongs to a single circle with probability about1/r². A mixed triple normally has only its own three supporters.
- Compute a circumcenter in translated coordinates. For u=B−A and v=C−A, the offset d satisfies d·u=|u|²/2 and d·v=|v|²/2. Solve using the cross-product determinant. Reject nearly collinear triples because their error is amplified. Reject non-finite and out-of-range results.
- Count points within radial tolerance0.001 using squared distances. Require at least8 supporters. Refit them with the circle equation X²+Y²=A·X+B·Y+C after centering at their mean. Pivoted3×3 Gaussian elimination gives A,B,C; center=mean+(A/2,B/2), radius²=C+(A²+B²)/4. Accept only if all support residuals≤0.0003. This reduces dependence on one noisy triple; tolerances are practical numerical safeguards, not a proof for adversarial noise.
- Remove points within0.0004 of an accepted circle, then repeat. If searches fail, add250 stars, filtering already explained ones. Retain at most2000 unexplained stars. Each search tries max(2000,40r²) triples. Enforce the100000 query cap and signal failure if evidence is insufficient, rather than inventing missing circles.
- Worked example: two interleaved populations come from (100,200,50) and (−150,−300,75). Three well-spaced stars from the first yield approximately(100,200,50); around half the500 stars support that hypothesis. Refit it and remove its supporters. A triple from the remaining population yields the second circle. The LOCAL example verifies both independent of order.
- This is explicitly probabilistic estimation. Finite samples can miss a circle; intersecting or near-tangent circumferences can confuse tolerance tests; poor angular coverage and adversarial allowed noise can destabilize estimates. Additional samples trade score for evidence without proving success. Official author programs also use randomized triple/vote methods. This independent implementation adds support/refinement and noise-aware checks; no full-score or hidden-judge acceptance claim is made.
Why it works
With exact data, a non-collinear same-circle triple uniquely determines its circle. Distinct circles meet in at most two points, so additional exact continuously sampled points eliminate mixed-triple coincidences with probability1. Repeated consensus extraction therefore recovers true circles with high probability. With noise and finite precision, residual checks and refinement are safeguards, not an absolute guarantee. The scored probabilistic nature and finite-cap failure path are intentionally disclosed.
Watch out. Submit without LOCAL. Report every circle once. Do not trust one triple, use floating equality, or fit nearly collinear points. The allowed10^−4 sample error exceeds the1e−6 reference tolerance, which cannot be assumed safe. Eight near-supporters are not a mathematical certificate for arbitrary noisy data. Uniform sampling does not guarantee every circle in every batch. Answer parameter bounds still apply. LOCAL checks are not official judge acceptance.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<random>
#include<stdexcept>
#include<utility>
#include<vector>
#ifndef LOCAL
#include"circle.h"
#else
std::pair<double,double>sample_star();
void answer(double x,double y,double radius);
#endif
using namespace std;
struct Point{
long double x;
long double y;
};
struct Circle{
long double x;
long double y;
long double radius;
};
long double distanceTo(const Point&p,const Circle&c){
return hypotl(p.x-c.x,p.y-c.y);
}
bool valid(const Circle&c){
return isfinite(c.x)&&isfinite(c.y)&&isfinite(c.radius)&&abs(c.x)<=500000&&abs(c.y)<=500000&&
c.radius>0&&c.radius<=500000;
}
bool belongs(const Point&p,const Circle&c,long double tolerance){
long double dx=p.x-c.x;
long double dy=p.y-c.y;
return abs(dx*dx+dy*dy-c.radius*c.radius)<=tolerance*(2*c.radius+tolerance);
}
bool throughThree(Point a,Point b,Point c,Circle&result){
long double ux=b.x-a.x;
long double uy=b.y-a.y;
long double vx=c.x-a.x;
long double vy=c.y-a.y;
long double determinant=ux*vy-uy*vx;
long double scale=max(ux*ux+uy*uy,vx*vx+vy*vy);
// Almost collinear triples amplify the allowed sampling error.
if(scale==0||abs(determinant)<0.08L*scale){
return false;
}
long double first=(ux*ux+uy*uy)/2;
long double second=(vx*vx+vy*vy)/2;
result.x=a.x+(first*vy-second*uy)/determinant;
result.y=a.y+(ux*second-vx*first)/determinant;
result.radius=distanceTo(a,result);
return valid(result);
}
bool refine(const vector<Point>&support,Circle&result){
Point mean{0,0};
for(Point p:support){
mean.x+=p.x/support.size();
mean.y+=p.y/support.size();
}
// Center coordinates before fitting X²+Y² = A*X+B*Y+C.
long double matrix[3][4]={};
for(Point p:support){
long double x=p.x-mean.x;
long double y=p.y-mean.y;
array<long double,3>row{x,y,1};
for(int i=0;i<3;++i){
for(int j=0;j<3;++j){
matrix[i][j]+=row[i]*row[j];
}
matrix[i][3]+=row[i]*(x*x+y*y);
}
}
for(int column=0;column<3;++column){
int pivot=column;
for(int row=column+1;row<3;++row){
if(abs(matrix[row][column])>abs(matrix[pivot][column])){
pivot=row;
}
}
if(abs(matrix[pivot][column])<1e-20L){
return false;
}
for(int j=column;j<4;++j){
swap(matrix[column][j],matrix[pivot][j]);
}
long double divisor=matrix[column][column];
for(int j=column;j<4;++j){
matrix[column][j]/=divisor;
}
for(int row=0;row<3;++row){
if(row!=column){
long double multiplier=matrix[row][column];
for(int j=column;j<4;++j){
matrix[row][j]-=multiplier*matrix[column][j];
}
}
}
}
long double x=matrix[0][3]/2;
long double y=matrix[1][3]/2;
long double squaredRadius=matrix[2][3]+x*x+y*y;
if(squaredRadius<=0){
return false;
}
result={mean.x+x,mean.y+y,sqrtl(squaredRadius)};
if(!valid(result)){
return false;
}
for(Point p:support){
if(!belongs(p,result,0.0003L)){
return false;
}
}
return true;
}
void solve(int k){
mt19937 random(481516);
vector<Point>points;
vector<Circle>found;
int queries=0;
while(int(found.size())<k&&queries<100000){
int batch=queries==0?500:250;
for(int i=0;i<batch&&queries<100000;++i){
auto coordinate=sample_star();
++queries;
Point p{coordinate.first,coordinate.second};
bool known=false;
for(const Circle&c:found){
known=known||belongs(p,c,0.0004L);
}
if(!known){
points.push_back(p);
}
}
// Retain bounded memory if rare samples require additional batches.
if(points.size()>2000){
shuffle(points.begin(),points.end(),random);
points.resize(2000);
}
bool progress=true;
while(progress&&int(found.size())<k){
progress=false;
int remaining=k-int(found.size());
int attempts=max(2000,40*remaining*remaining);
if(points.size()<8){
break;
}
uniform_int_distribution<int>pick(0,int(points.size())-1);
for(int trial=0;trial<attempts;++trial){
Circle hypothesis;
if(!throughThree(
points[pick(random)],points[pick(random)],points[pick(random)],hypothesis)){
continue;
}
vector<Point>support;
for(Point p:points){
if(belongs(p,hypothesis,0.001L)){
support.push_back(p);
}
}
if(support.size()<8||!refine(support,hypothesis)){
continue;
}
found.push_back(hypothesis);
points.erase(remove_if(points.begin(),points.end(),
[&](Point p){
return belongs(p,hypothesis,0.0004L);
}),
points.end());
progress=true;
break;
}
}
}
// Never invent missing circles after the sampling limit.
if(int(found.size())!=k){
throw runtime_error("Insufficient reliable samples before the query limit");
}
for(const Circle&c:found){
answer(double(c.x),double(c.y),double(c.radius));
}
}
#ifdef LOCAL
vector<Circle>hiddenCircles;
vector<Circle>reported;
mt19937_64 starRandom;
int starQueries=0;
long double noiseBound=0;
pair<double,double>sample_star(){
if(++starQueries>100000){
throw runtime_error("Sample limit exceeded");
}
uniform_int_distribution<int>choose(0,int(hiddenCircles.size())-1);
uniform_real_distribution<long double>angle(0,2*acosl(-1));
uniform_real_distribution<long double>noise(-noiseBound,noiseBound);
const Circle&c=hiddenCircles[choose(starRandom)];
long double theta=angle(starRandom);
long double radius=c.radius+noise(starRandom);
return {double(c.x+radius*cosl(theta)),double(c.y+radius*sinl(theta))};
}
void answer(double x,double y,double radius){
reported.push_back({x,y,radius});
}
int main(){
int k;
unsigned long long seed;
cin>>k>>seed>>noiseBound;
hiddenCircles.resize(k);
for(Circle&c:hiddenCircles){
cin>>c.x>>c.y>>c.radius;
}
starRandom.seed(seed);
solve(k);
vector<bool>used(k);
if(int(reported.size())!=k){
throw runtime_error("Wrong answer count");
}
for(const Circle&c:reported){
int match=-1;
for(int i=0;i<k;++i){
const Circle&actual=hiddenCircles[i];
if(!used[i]&&abs(c.x-actual.x)<=0.001L&&abs(c.y-actual.y)<=0.001L&&
abs(c.radius-actual.radius)<=0.001L){
match=i;
}
}
if(match<0){
throw runtime_error("Circle outside parameter tolerance");
}
used[match]=true;
}
cout<<"Correct\n";
cerr<<"samples="<<starQueries<<'\n';
}
#endif