POJ 1971 Parallelogram Counting
問題
2次元平面上の整数座標がn点(n<=1000)与えられる。4点を選んでできる平行四辺形の個数を求めよ。ただしどの4点も一直線上に並ばないものとする。
やりかた
3点を指定すると残り1点が定まり、その残りの点が与えられた中にあるかを調べる、というやりかただとTLEしてしまう。
2点を指定するとその2点の中点が定まる。このとき別の2点の中点がこの中点と同じだとすると、そこで一つの平行四辺形ができる。こう考えると、2点の中点をすべて列挙し、とある中点がkペアの2点の中点となっていたら、その中点を中心に個の平行四辺形ができるわけだから、これを足し上げていけばいい。計算量
ただ、G++で中点の頻度を
map<pair<long long, long long>, int>
で管理したらTLEしたのですこし工夫した。あと、中点は整数になっていてほしいので得られた座標を原点基準で2倍することで必ず中点が整数になるようにしている。
以下ソース。
ll x[1000], y[1000]; ll base = 5000000000; int main(){ int t; scanf("%d", &t); while(t--){ int n; scanf("%d", &n); for(int i = 0; i < n; i++){ scanf("%lld %lld", x + i, y + i); x[i] *= 2LL; y[i] *= 2LL; } int idx = 0; vector<ll> p(n * (n - 1) / 2); for(int i = 0; i < n; i++){ for(int j = i + 1; j < n; j++){ ll cx = (x[i] + x[j]) / 2; ll cy = (y[i] + y[j]) / 2; p[idx++] = cy * base + cx; } } sort(ALL(p)); int c = 1; int ans = 0; for(int i = 1; i < p.size(); i++){ if(p[i] == p[i - 1]) c++; else{ ans += (c * (c - 1) / 2); c = 1; } } ans += (c * (c - 1) / 2); cout << ans << endl; } return 0; }
1000msくらいだった
Get up! 明日のSUPER ST@R!