2167-Find the Point

問題和訳

直線の集合が与えられる．全ての直線から等距離にある点を求めよ．ただし，そのような点が2つ以上ある場合は"Many",全く無い場合は"None"と答えよ．

解法

まず直線が2つの時を考える．
直線が二つの時，両方の直線から等距離にある点の集合は次の図の青色部分のようになる．

次にある程度の個数の直線(全部調べるとTLEする)について，それぞれ2つの場合の時の点の集合(直線になる)を求めて，その交点を候補とする．

最後に候補について，全ての直線から等距離にあるものがいくつあるのかを数える．

実装(C++)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <complex>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <boost/format.hpp>
using namespace std;

const double EPS=1e-4;
const double INF=1e10;


typedef complex<double> Point;
inline double cross(const Point &a,const Point &b){return imag(conj(a)*b);}
inline double dot(const Point &a,const Point &b){return real(conj(a)*b);}
inline double atan(const Point &a){return atan2(imag(a),real(a));}
inline Point unit(const Point &a){return a*(1/abs(a));}
namespace std{
	bool operator<(const Point &a,const Point &b){return real(a)==real(b)?imag(a)<imag(b):real(a)<real(b);}
	Point operator*(const Point &a,const double &b){return Point(real(a)*b,imag(a)*b);}
}
struct Line:vector<Point>{
	Line(double x1=0,double y1=0,double x2=0,double y2=0){
		(*this).push_back(Point(x1,y1));
		(*this).push_back(Point(x2,y2));
	}
	Line(Point a,Point b){
		(*this).push_back(a);(*this).push_back(b);
	}
};

int ccw(Point a,Point b,Point c){
    b-=a;c-=a;
    if(cross(b, c)>0)return +1;       // counter clockwise
    if(cross(b, c)<0)return -1;       // clockwise
    if(dot(b, c)<0)return +2;       // c--a--b on line
    if(norm(b)<norm(c))return -2;       // a--b--c on line
    return 0;
}

bool is_intersect_LL(const Line &l, const Line &m) {
	return abs(cross(l[1]-l[0], m[1]-m[0])) > EPS || // non-parallel
			abs(cross(l[1]-l[0], m[0]-l[0])) < EPS;   // same line
}
bool is_intersect_LS(const Line &l, const Line &s) {
	return cross(l[1]-l[0], s[0]-l[0])*       // s[0] is left of l
			cross(l[1]-l[0], s[1]-l[0]) < EPS; // s[1] is right of l
}
bool is_intersect_LP(const Line &l, const Point &p) {
	return abs(cross(l[1]-p, l[0]-p)) < EPS;
}
Point projection(const Line &l, const Point &p) {
	double t = dot(p-l[0], l[0]-l[1]) / norm(l[0]-l[1]);
	return l[0] + t*(l[0]-l[1]);
}
Point reflection(const Line &l, const Point &p) {
	return p + (projection(l, p) - p)*2;
}
double distance_LP(const Line &l, const Point &p) {
	return abs(p - projection(l, p));
}
double distance_LL(const Line &l, const Line &m) {
	return is_intersect_LL(l, m) ? 0 : distance_LP(l, m[0]);
}
Point crosspoint_LL(const Line &l, const Line &m) {
	double A = cross(l[1] - l[0], m[1] - m[0]);
	double B = cross(l[1] - l[0], l[1] - m[0]);
	if (abs(A) < EPS && abs(B) < EPS) return m[0]; // same line
	return m[0] + B / A * (m[1] - m[0]);
}

istream &operator>>(istream &is,Line &a){
	for(int i=0;i<2;i++)is>>a[i].real()>>a[i].imag();
	return is;
}
int N;
Line lines[100];
bool input(){
	if(!(cin>>N))return false;
	if(N==0)return false;
	for(int i=0;i<N;i++){
		cin>>lines[i];
	}
	return true;
}
void make_line(Line &a,Line &b,vector<Line> &candidate){
	if(is_intersect_LL(a,b)==false){
		//平行の場合2本の中間にする
		//通る二点は適当に決める
		Line c((a[0]+projection(b,a[0]))*.5,(a[1]+projection(b,a[1]))*.5);
		candidate.push_back(c);
	}else{
		Point cp=crosspoint_LL(a,b);
		Point n1=cp+unit(a[1]-a[0]),n2=cp-unit(a[1]-a[0]),n3=cp+unit(b[1]-b[0]);
		candidate.push_back(Line(cp,(n1+n3)*.5));
		candidate.push_back(Line(cp,(n2+n3)*.5));
	}
}
bool check(const Point &p){
	double dist=distance_LP(lines[0],p);
	for(int i=1;i<N;i++){
		if(abs(distance_LP(lines[i],p)-dist)>EPS)return false;
	}
	return true;
}
void add_point(const Point &a,vector<Point> &pts){
	pts.push_back(a);
}
int main() {
	while(input()){
		vector<Line> candidate;//線の候補
		for(int i=0;i<N;i++){
			for(int j=i+1;j<N;j++){
				make_line(lines[i],lines[j],candidate);
			}
		}
		candidate.push_back(lines[0]);
		vector<Point> pts; //点の候補
		bool checked=false;
		for(int i=0;i<min<int>(candidate.size(),4);i++){
			for(int j=i+1;j<(int)candidate.size();j++){
				if(is_intersect_LL(candidate[i],candidate[j])){
					add_point(crosspoint_LL(candidate[i],candidate[j]),pts);
					checked=true;
				}
			}
			add_point(candidate[i][0],pts);
			add_point(candidate[i][1],pts);
		}
		int ans_count=0;
		Point ans_point;
		for(int i=0;i<(int)pts.size();i++){
			if(check(pts[i])){
				if(ans_count){
					if(abs(ans_point-pts[i])<EPS)continue;
				}
				ans_count++;
				ans_point=pts[i];
			}
		}
		if(ans_count==0){
			cout<<"None"<<endl;
		}else if(ans_count==1){
			cout<<boost::format("%.6f %.6f")%ans_point.real()%ans_point.imag()<<endl;
		}else{
			cout<<"Many"<<endl;
		}
	}
	return 0;
}