TopCoder SRM Div1 Medium CentersOfSymmetry

問題

n本の相異なる直線が与えられる。
n本の直線の集合の、点対称の中心の個数を求めよ。
無限にある場合は-1を返せ。

制約条件

n≦50
直線はその直線が通る2点の座標により与えられる。
点は全て格子点である。

方針

まずは点対称の中心が無限にあるかを見る。
平行な直線a, bについて、
その真ん中の線上の点がその候補。

その中で適当な座標が無理数な点を取ってやって、
その点に関して全ての点を対称移動してやって、直線の集合が元と一致するかを見る。

次に対称中心が1点の場合。
直線同士の交点は、これもまた点対称になっているはず。
なので、直線の交点の全ての中心が対称中心の候補。
この点に関して全ての点を対称移動して、直線の集合が元と一致するか見る。

ソースコード

struct L : public vector<P> {
	double a, b, c;
  L(const P &p1, const P &p2) {
    push_back(p1); push_back(p2);
    
		double dx = p2.real() - p1.real();
		double dy = p2.imag() - p1.imag();
		a = dx;
		b = -dy;
		c = -p1.imag() * dx + p1.real() * dy;
	
		if(a) b /= a, c /= a, a = 1;
		else a /= b, c /= b, b = 1;
	}
	bool operator==(const L &o)const{
		return abs(a - o.a) < EPS && abs(b - o.b) < EPS && abs(c - o.c) < EPS;
	}
	bool operator<(const L &o)const{
		if(abs(a - o.a) > EPS) return a < o.a;
		if(abs(b - o.b) > EPS) return b < o.b;
		return c + EPS < o.c;
  }
};
P ref(const P &p, const P &o){
	return 2.0 * o - p;
}

class CentersOfSymmetry {
  public:
  int lineConfigurations(vector <int> x1, vector <int> y1, vector <int> x2, vector <int> y2) {
		int n = x1.size();
		
		if(n == 1) return -1;
		
		set<L> s;
		vector<P> p1, p2;
		vector<P> cs;
		
		rep(i, n) p1.pb(P(x1[i], y1[i])), p2.pb(P(x2[i], y2[i]));
		rep(i, n) s.insert(L(p1[i], p2[i]));
		
		rep(i, n) rep(j, i){
			if(!intersectLL(L(p1[i], p2[i]), L(p1[j], p2[j]))){
				P q1 = (p1[i] + p1[j]) * 0.5, q2 = (p2[i] + p2[j]) * 0.5;
				
				if(abs(q1 - q2) < EPS){
					q1 = (p1[i] + p2[j]) * 0.5;
					q2 = (p2[i] + p1[j]) * 0.5;
				}
				
				P o = q1 * sqrt(2.0) + q2 * (1 - sqrt(2.0));
				set<L> ss;
				rep(k, n){
					P r1 = ref(p1[k], o), r2 = ref(p2[k], o);
					ss.insert(L(r1, r2));
				}
				if(s == ss) return -1;
			}
			else{
				P p = crosspoint(L(p1[i], p2[i]), L(p1[j], p2[j]));
				cs.pb(p);
			}
		}
		if(cs.empty()) return 0;
		P o;
		rep(i, cs.size()) o += cs[i];
		o *= 1.0 / cs.size();
		
		set<L> ss;
		rep(i, n){
			P r1 = ref(p1[i], o), r2 = ref(p2[i], o);
			ss.insert(L(r1, r2));
		}
		return s == ss ? 1 : 0;
  }
};