AOJ 2167: Find the Point

robustness-hard。いい練習になる。
気をつけないといけないことは、
・点が少ないときのMany
・平行のとき(中点を結んで線を作ろうとすると長さが極端に短くなって誤差る)
・交わるとき(点をいいかげんに選ぶとargを取るときに長さが極端に短くなって誤差る)
最初の3つの直線で候補の点を絞って、これを全探索しました。

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
using namespace std;
const double EPS = 1e-6;
/*  */
Pt p1[110];
Pt p2[110];
double rd[100];
double ld[100];
int main(){
	int a;
	while(scanf("%d",&a),a){
		for(int i=0;i<a;i++){
			double X1,X2,Y1,Y2;
			scanf("%lf%lf%lf%lf",&X1,&Y1,&X2,&Y2);
			p1[i]=Pt(X1,Y1);
			p2[i]=Pt(X2,Y2);
		}
		if(a<=2){
			printf("Many\n");continue;
		}
		if(iLL(p1[0],p2[0],p1[1],p2[1])==0&&iLL(p1[1],p2[1],p1[2],p2[2])==0){
			printf("None\n");continue;
		}
		vector<pair<Pt,Pt> >L1;
		vector<pair<Pt,Pt> >L2;
		if(iLL(p1[0],p2[0],p1[1],p2[1])==0){
			Pt L=(p1[0]+p1[1])/2;
			Pt R=(p2[0]+p2[1])/2;
			if((L-R).ABS()<1.0){
				L=(p1[0]+p2[1])/2;
				R=(p2[0]+p1[1])/2;
			}
			L1.push_back(make_pair(L,R));
		}else{
			Pt p=pLL(p1[0],p2[0],p1[1],p2[1]);
			double th=0;
			if((p2[0]-p).ABS()>1)th+=((p2[0]-p).arg());
			else th+=((p1[0]-p).arg());
			if((p2[1]-p).ABS()>1)th+=((p2[1]-p).arg());
			else th+=((p1[1]-p).arg());
			th/=2;
			L1.push_back(make_pair(p,p+Pt(cos(th),sin(th))*1000.0));
			L1.push_back(make_pair(p,p+Pt(cos(th+PI/2),sin(th+PI/2))*1000.0));
		}
		if(iLL(p1[2],p2[2],p1[1],p2[1])==0){
			Pt L=(p1[2]+p1[1])/2;
			Pt R=(p2[2]+p2[1])/2;
			if((L-R).ABS()<1.0){
				L=(p1[2]+p2[1])/2;
				R=(p2[2]+p1[1])/2;
			}
			L2.push_back(make_pair(L,R));
		}else{
			Pt p=pLL(p1[2],p2[2],p1[1],p2[1]);
			double th=0;
			if((p2[2]-p).ABS()>1)th+=((p2[2]-p).arg());
			else th+=((p1[2]-p).arg());
			if((p2[1]-p).ABS()>1)th+=((p2[1]-p).arg());
			else th+=((p1[1]-p).arg());
			th/=2;
			L2.push_back(make_pair(p,p+Pt(cos(th),sin(th))*1000.0));
			L2.push_back(make_pair(p,p+Pt(cos(th+PI/2),sin(th+PI/2))*1000.0));
		}
	//	printf("%d %d\n",L1.size(),L2.size());
		vector<Pt>hb;
		for(int i=0;i<L1.size();i++)for(int j=0;j<L2.size();j++){
		//	if(iLL(L1[i].first,L1[i].second,L2[j].first,L2[j].second)!=1)printf("Alert\n");
			hb.push_back(pLL(L1[i].first,L1[i].second,L2[j].first,L2[j].second));
		}
		int ans=0;
		for(int i=0;i<hb.size();i++){
	//		printf("%f %f: ",hb[i].x,hb[i].y);
			bool dame=false;
			for(int j=0;j<i;j++){
				if((hb[i]-hb[j]).ABS()<EPS){
					dame=true;
				}
			}
			if(dame){
				rd[i]=1;ld[i]=0;continue;
			}
			rd[i]=-999999999;ld[i]=999999999;
			for(int j=0;j<a;j++){
				double dist=dLP(p1[j],p2[j],hb[i]);
				rd[i]=max(rd[i],dist);
				ld[i]=min(ld[i],dist);
			//	printf("%f ",dist);
			}//printf("\n");
			if(rd[i]-ld[i]<EPS)ans++;
		}
		if(ans>1)printf("Many\n");
		else if(ans==0)printf("None\n");
		else{
			for(int i=0;i<hb.size();i++){
				if(rd[i]-ld[i]<EPS)printf("%f %f\n",hb[i].x,hb[i].y);
			}
		}
	}
}