EducationalCF50 E - Covered Points

問題

線分がn本与えられる
これらのうち1本以上が通る格子点の個数を求めよ
ただし異なる2本の線分は交差することはあるが同一直線上にあることはない

1 <= n <= 1000
ー10^6 <= x,y <= 10^6

解法

まず線分ごとに格子点の数を計算して足し合わせる
(x1,y1)と(x2,y2)を結んだ線分上の格子点の個数は|x1-x2|と|y1-y2|のgcd+1 (蟻本p107)
で、これだけだとある格子点で2本以上の線分が交差してる場合、交差してる線分の本数-1回だけ重複してカウントしちゃってるから、そのぶん引く必要がある
二重ループで異なる2本の線分のペアを全て見て、それらが交点を持ちかつそれが格子点である場合だけ答えを-1すればいい
ただしこの時にも重複に気をつける必要がある
例えば3本の線分がある格子点で交差しているとき、最初に重複してカウントしたのは2回分だけど、異なる2本の線分のペアは3個あり、何も対策しないと3回答えを-1してしまう
これを防ぐには一度見た交点をsetに入れておけばいい

ダメな例)
1本目の線分から見て、2本目の線分と3本目の線分それぞれと交差してるから答えを-2する
→ 2本目の線分から見て、3本目の線分と交差してるから答えを-1する
→ トータル-3

良い例)
1本目の線分から見て、2本目の線分と3本目の線分それぞれと交差してるから答えを-2し、これらの交点をsetに入れる
→ 2本目の線分から見て、3本目の線分と交差してるけどその座標はsetに入ってるから何もしない
→ トータル-2

実装

intls: 線分の交差判定
pintls: 線分同士の交点を求める
deq: double型同士の同値判定(1e-10以下の誤差を認める)

i本目の線分から見た時、j本目の線分との交点とk(>j)本目の線分との交点が同じ点の場合にはどっちも答えを-1する必要があって、すぐにsetに突っ込んだらまずいから、とりあえずvectorに突っ込んで一周してからsetに入れてる

typedef complex<double> P;

int n, res;
P a[1010], b[1010];
set<pair<int,int> > us;

signed main() {
	cin >> n;
	rep(i,n) {
		int ax, ay, bx, by;
		cin >> ax >> ay >> bx >> by;
		res += gcd(abs(ax-bx), abs(ay-by)) + 1;
		a[i] = P(ax,ay), b[i] = P(bx,by);
	}
	rep(i,n) {
		vector<pair<int,int>> lst;
		reps(j,i+1,n) {
			if (!intls(a[i],b[i],a[j],b[j])) continue;
			P p = pintls(a[i],b[i],a[j],b[j]);
			if (deq(p.real(), round(p.real())) && deq(p.imag(), round(p.imag()))) {
				pair<int,int> t = {(int)round(p.real()), (int)round(p.imag())};
				if (us.count(t)) continue;
				res--;
				lst.push_back(t);
			}
		}
		each(i,lst) us.insert(i);
	}
	cout << res << endl;
}