Codeforces ECR #050 : E. Covered Points

ライブラリで殴った感がある。
http://codeforces.com/contest/1036/problem/E

問題

２次元座標系において、互いに同一直線上にない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;
	
}

まとめ

幾何問題はほんと面倒だ。