ライブラリで殴った感がある。
http://codeforces.com/contest/1036/problem/E
問題
2次元座標系において、互いに同一直線上にないN個の線分が与えられる。
1個以上の線分が通過する格子点はいくつあるか。
解法
個々の線分が通る格子点数の総和は容易に求められる。
あとは複数の線分で共有される格子点を求め、引いていこう。
幸いNは小さいので、O(N^2)かけて線分の対を総当たりし、交点とそこを通る線分数を列挙しよう。
交点のうち格子点上にあり、そこをm個の線分が通過するなら、解からm-1を引いていけばよい。
線分の交点は面倒だけど適当な幾何ライブラリでどうにかする。
int N; ll X[1010][2],Y[1010][2]; ll ret; map<pair<int,int>,set<int>> M; typedef complex<double> Po; struct Line { Po a,b; void Rep(){ // assert(a!=b); if(a.real()==b.real()) { a.imag(0);b.imag(1); return;} // Y-axis Po c,d; d.real(1); d.imag((b.imag()-a.imag())/(b.real()-a.real())); c.imag(b.imag()-b.real()*d.imag()); d.imag(d.imag()+c.imag()); a=c; b=d; }; }; Po CrossPoint(const Line &l,const Line &r) { Po p,ld=l.b-l.a,rd=r.b-r.a,d3=l.b-r.a; double aa=ld.real()*rd.imag()-ld.imag()*rd.real(); double bb=ld.real()*d3.imag()-ld.imag()*d3.real(); if(abs(aa)<1e-9 && abs(bb)<1e-9) return Po(1e9,-1e9); //same if(abs(aa)<1e-9) return Po(1e9,1e9); //parallel return r.a+bb/aa*(r.b-r.a); }; Line L[1010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) { cin>>X[i][0]>>Y[i][0]>>X[i][1]>>Y[i][1]; L[i].a.real(X[i][0]); L[i].a.imag(Y[i][0]); L[i].b.real(X[i][1]); L[i].b.imag(Y[i][1]); L[i].Rep(); ll a=abs(X[i][1]-X[i][0]); ll b=abs(Y[i][1]-Y[i][0]); ret+=1+__gcd(a,b); } FOR(i,N) FOR(j,i) { Po p=CrossPoint(L[i],L[j]); double x=p.real(),y=p.imag(); ll xa=round(x); ll ya=round(y); if(xa<X[i][0]&&xa<X[i][1]) continue; if(xa>X[i][0]&&xa>X[i][1]) continue; if(ya<Y[i][0]&&ya<Y[i][1]) continue; if(ya>Y[i][0]&&ya>Y[i][1]) continue; if(xa<X[j][0]&&xa<X[j][1]) continue; if(xa>X[j][0]&&xa>X[j][1]) continue; if(ya<Y[j][0]&&ya<Y[j][1]) continue; if(ya>Y[j][0]&&ya>Y[j][1]) continue; if((xa-X[i][0])*(Y[i][1]-Y[i][0])-(X[i][1]-X[i][0])*(ya-Y[i][0])) continue; if((xa-X[j][0])*(Y[j][1]-Y[j][0])-(X[j][1]-X[j][0])*(ya-Y[j][0])) continue; M[{xa,ya}].insert(i); M[{xa,ya}].insert(j); } FORR(m,M) ret-=m.second.size()-1; cout<<ret<<endl; }
まとめ
幾何問題はほんと面倒だ。