【XR-4】尺规作图

题目背景

这是一道提交答案(人类智慧)题。 由于洛谷现在不支持提交答案,本题采用传统题的模式。 **赛时提醒:[下发文件](http://www.xht37.com/wp-content/uploads/2019/10/XR-4-G-update.zip)有更新。**

题目描述

你有若干个已知的几何图形,你需要通过尺规作图得到一个要求的点。你需要在规定步数之内找到这个点。 你可以进行的操作如下: 1. 以一个已知点为圆心,另一个已知点为圆上一点作圆。 2. 连接两个已知点形成一条直线。 你需要输出你的作图步骤。

输入输出格式

输入格式


第一行一个整数,表示测试点编号。 第二行一个整数 $n$,表示已知点的数量。 接下来 $n$ 行,第 $i$ 行两个实数 $x_i, y_i$,表示第 $i$ 个点的坐标。 接下来一个整数 $n_1$,表示已知线段的数量。 接下来 $n_1$ 行,每一行两个整数 $u, v$,表示有一条连接点 $u$ 和点 $v$ 的线段。 接下来一个整数 $n_2$,表示已知直线的数量。 接下来 $n_2$ 行,每一行两个整数 $u, v$,表示有一条经过点 $u$ 和点 $v$ 的直线。 接下来一个整数 $n_3$,表示已知圆的数量。 接下来 $n_3$ 行,每一行两个整数 $u, v$,表示有一个以点 $u$ 为圆心,点 $v$ 为圆上一点的圆。 接下来两个实数 $x, y$,表示要求点的坐标。 接下来 $10$ 个整数 $a_1$ 到 $a_{10}$,表示此测试点的评分参数,详见说明。

输出格式


第一行一个整数 $m$,表示你需要的步数。 接下来 $m$ 行描述你的作图步骤: 首先一个整数 $1$ 或 $2$,$1$ 表示你要画一个圆,$2$ 表示你要连一条直线。 接下来四个实数 $x_1, y_1, x_2, y_2$: 如果你要画一个圆,表示你要以 $(x_1,y_1)$ 为圆心,$(x_2,y_2)$ 为圆上一点画圆; 如果你要连一条线,表示你要将 $(x_1,y_1)$ 与 $(x_2,y_2)$ 连接起来。

输入输出样例

输入样例 #1

2
0.0000000000 0.0000000000
0.0000000000 1.0000000000
1
1 2
0
0
0.8660254038 0.5000000000
11 10 9 8 7 6 5 4 3 2

输出样例 #1

2
1 0.0000000000 0.0000000000 0.0000000000 1.0000000000
1 0.0000000000 1.0000000000 0.0000000000 0.0000000000

说明

对于每一个测试点,如果你用的步数小于等于前 $i$ 个评分参数,那么你会得到 $i$ 分。 注意事项如下: 1. **所有的 $x, y$ 必须是你已经得到的点**,这里的已经得到是指输入数据中的点或者已知几何图形的交点。(也就是说你不能随便选择一个点来作图,也不能通过选择一个合适的点来得到要求的点) 更准确地说,每次你输出一个坐标,Special Judge 会选择当前你已经得到的所有点中和你的输入坐标欧几里得距离最近的点作为你这一次的选择点。如果距离最近的点距离大于了 $10^{-5}$,那么这次操作会被判定为不合法,同时这一个点你将得到 $0$ 分。 2. 你不能根据圆心和半径作圆,而只能根据圆心和圆上一点作圆。 3. **你画出的答案与要求的点绝对误差或相对误差不超过 $10^{-5}$ 即为正确**(因为不知道怎么写没有误差的 Special Judge)。 更准确地说,假设你得到的点是 $(x_1, y_1)$,而要求的点是 $(x_2, y_2)$,则你的输出被认为正确,当且仅当 $\dfrac{|x_1-x_2|}{\max(|x_2|, 1)} \le 10^{-5}$ 且 $\dfrac{|y_1-y_2|}{\max(|y_2|, 1)} \le 10^{-5}$。 4. 下发文件中的 `data1.in` 到 `data10.in` 分别为 $10$ 个输入数据,其中第 $1,2,3,7,8$ 这五个测试点配有图解。 5. 下发的 checker 可以判断你的得分。使用方法如下(其中 `data.in` 是输入文件,`data.out` 是你的输出文件。): - Windows-32/64: ``` checker data.in data.out data.out ``` - Linux/MacOS: ``` ./checker data.in data.out data.out ``` 6. 出题人拿不到 $100$ 分。 update:checker 源码如下,如果有需要改进的地方欢迎提出: ```cpp #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include"testlib.h" using namespace std; const double Pi=acos(-1.0); const double EPS=1e-9; int sign(double a){return a<-EPS?-1:a>EPS;} int sign2(double a){return a<-1e-5?-1:a>1e-5;} int cmp(double a,double b){return sign(a-b);} int cmp2(double a,double b){return sign2(a-b);} struct Point { double x,y; Point(double xx=0,double yy=0){x=xx,y=yy;} Point operator+(Point p){return Point(x+p.x,y+p.y);} Point operator-(Point p){return Point(x-p.x,y-p.y);} Point operator*(double d){return Point(x*d,y*d);} Point operator/(double d){return Point(x/d,y/d);} double operator==(Point p){return cmp(x,p.x)==0&&cmp(y,p.y)==0;} double dot(Point p){return x*p.x+y*p.y;} double det(Point p){return x*p.y-y*p.x;} double abs2(){return x*x+y*y;} double abs(){return sqrt(abs2());} Point unit(){return *this/abs();} Point rot90(){return Point(-y,x);} }p[1000005],goal; int o[1005],p1[1005],p2[1005],numc,numl,tot,nums,a[15]; double d[1005]; bool flag; bool cmp(Point a,Point b) { if(fabs(a.x-b.x)/max(1.0,fabs(b.x))<=1e-5&&fabs(a.y-b.y)/max(1.0,fabs(b.y))<=1e-5)return 1; else return 0; } double dis(Point p1,Point p2){return (p2-p1).abs();} double disLP(Point p1,Point p2,Point p) { return fabs((p-p1).det(p2-p1)/(p2-p1).abs()); } bool onLine(Point p1,Point p2,Point p) { return disLP(p1,p2,p)<EPS; } bool isMiddle(double a,double m,double b) { if(a>b)swap(a,b); return cmp(a,m)!=1&&cmp(m,b)!=1; } bool isMiddle(Point a,Point m,Point b) { return isMiddle(a.x,m.x,b.x)&&isMiddle(a.y,m.y,b.y); } Point isLL(Point p1,Point p2,Point q1,Point q2) { double d1=(q2-q1).det(p2-q1); double d2=(p1-q1).det(q2-q1); return p1+(p2-p1)/(d1+d2)*d2; } pair<Point,Point>isCL(Point o,double r,Point p1,Point p2) { double d=(p2-p1).det(p2-o)/(p2-p1).abs(); Point m=o+(p2-p1).rot90().unit()*d; d=(m-o).abs2(); d=r*r-d; d=max(d,0.0); d=sqrt(d); Point dr=(p2-p1).unit()*d; return make_pair(m-dr,m+dr); } pair<Point,Point>isCC(Point o1,double r1,Point o2,double r2) { double d=(o2-o1).abs2(); double cosc=(r1*r1+d-r2*r2)/(2*sqrt(d)*r1); d=cosc*r1; Point m=o1+(o2-o1).unit()*d; d=r1*r1-(m-o1).abs2(); d=max(d,0.0); d=sqrt(d); Point dr=(o2-o1).unit().rot90()*d; return make_pair(m+dr,m-dr); } void ins_C(int x,double r) { o[++numc]=x; d[numc]=r; for(int i=1;i<=numc;i++) { if(dis(p[o[numc]],p[o[i]])>d[numc]+d[i]+EPS)continue; if(dis(p[o[numc]],p[o[i]])<fabs(d[numc]-d[i])+EPS)continue; pair<Point,Point>ans=isCC(p[o[i]],d[i],p[o[numc]],d[numc]); for(int i=1;i<=tot;i++) { if(p[i]==ans.first)break; if(i==tot)p[++tot]=ans.first; } for(int i=1;i<=tot;i++) { if(p[i]==ans.second)break; if(i==tot)p[++tot]=ans.second; } if(cmp(ans.first,goal))flag=1; if(cmp(ans.second,goal))flag=1; } for(int i=1;i<=numl;i++) { if(disLP(p[p1[i]],p[p2[i]],p[o[numc]])>r+EPS)continue; pair<Point,Point>ans=isCL(p[o[numc]],r,p[p1[i]],p[p2[i]]); if(i<=nums&&!isMiddle(p[p1[i]],ans.first,p[p2[i]]))ans.first=Point(0,0); if(i<=nums&&!isMiddle(p[p1[i]],ans.second,p[p2[i]]))ans.second=Point(0,0); for(int i=1;i<=tot;i++) { if(p[i]==ans.first)break; if(i==tot)p[++tot]=ans.first; } for(int i=1;i<=tot;i++) { if(p[i]==ans.second)break; if(i==tot)p[++tot]=ans.second; } if(cmp(ans.first,goal))flag=1; if(cmp(ans.second,goal))flag=1; } } void ins_L(int pp1,int pp2) { p1[++numl]=pp1; p2[numl]=pp2; for(int i=1;i<=numc;i++) { if(disLP(p[p1[numl]],p[p2[numl]],p[o[i]])>d[i]+EPS)continue; pair<Point,Point>ans=isCL(p[o[i]],d[i],p[p1[numl]],p[p2[numl]]); for(int j=1;j<=tot;j++) { if(p[j]==ans.first)break; if(j==tot)p[++tot]=ans.first; } for(int j=1;j<=tot;j++) { if(p[j]==ans.second)break; if(j==tot)p[++tot]=ans.second; } if(cmp(ans.first,goal))flag=1; if(cmp(ans.second,goal))flag=1; } for(int i=1;i<numl;i++) { if(sign((p[p2[numl]]-p[p1[numl]]).det(p[p2[i]]-p[p1[i]]))==0)continue; Point ans=isLL(p[p1[numl]],p[p2[numl]],p[p1[i]],p[p2[i]]); if(i<=nums&&!isMiddle(p[p1[i]],ans,p[p2[i]]))ans=Point(0,0); for(int j=1;j<=tot;j++) { if(p[j]==ans)break; if(j==tot)p[++tot]=ans; } if(cmp(ans,goal))flag=1; } } int main(int argc,char*argv[]) { registerTestlibCmd(argc, argv); tot=inf.readInt(); tot=inf.readInt(); for(int i=1;i<=tot;i++) { p[i].x=inf.readDouble(); p[i].y=inf.readDouble(); } nums=inf.readInt(); for(int i=1;i<=nums;i++) { int x=inf.readInt(),y=inf.readInt(); ins_L(x,y); } int n=inf.readInt(); for(int i=1;i<=n;i++) { int x=inf.readInt(),y=inf.readInt(); ins_L(x,y); } n=inf.readInt(); for(int i=1;i<=n;i++) { int x=inf.readInt(),y=inf.readInt(); ins_C(x,dis(x,y)); } goal.x=inf.readDouble(); goal.y=inf.readDouble(); for(int i=1;i<=10;i++)a[i]=inf.readInt(); int m=ouf.readInt(0,2147483647); if(m>a[1]) { quitf(_wa,"too many steps.a[1] is %d,your answer is %d",a[1],m); return 0; } flag=0; for(int o=1;o<=m;o++) { int type=ouf.readInt(1,2); double x1=ouf.readDouble(),y1=ouf.readDouble(),x2=ouf.readDouble(),y2=ouf.readDouble(); int p1=0,p2=0; double minn=1e100; for(int i=1;i<=tot;i++) { if(dis(p[i],Point(x1,y1))<minn) { minn=dis(p[i],Point(x1,y1)); p1=i; } } if(minn>1e-5)quitf(_wa,"point(%.8lf,%.8lf) not found",x1,y1); minn=1e100; for(int i=1;i<=tot;i++) { if(dis(p[i],Point(x2,y2))<minn) { minn=dis(p[i],Point(x2,y2)); p2=i; } } if(minn>1e-5)quitf(_wa,"point(%.8lf,%.8lf) not found",x2,y2); if(p1==p2)quitf(_wa,"point(%.8lf,%.8lf) and point(%.8lf %.8lf) coincide",x1,y1,x2,y2); if(type==1)ins_C(p1,dis(p[p1],p[p2])); else ins_L(p1,p2); if(flag==1) { int x=1; while(m<=a[x])x++; x--; if(x==10) { quitf(_ok,"Perfect Answer.your answer is %d",m); return 0; } quitp(x/10.0,"Partially Correct get %d percent",x); return 0; } } quitf(_wa,"point(%.8lf,%.8lf) not found",goal.x,goal.y); return 0; } ```