結果
問題 |
No.1144 Triangles
|
ユーザー |
![]() |
提出日時 | 2020-07-31 21:56:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 647 ms / 3,000 ms |
コード長 | 1,285 bytes |
コンパイル時間 | 1,742 ms |
コンパイル使用メモリ | 174,804 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-06 17:53:23 |
合計ジャッジ時間 | 10,802 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 25 |
ソースコード
#include <bits/stdc++.h> int ri() { int n; scanf("%d", &n); return n; } #define MOD 1000000007 #define PI 3.1415926535897932384626 double my_atan2(int x, int y) { double res = std::atan2(y, x); if (res < 0) res += PI * 2; return res; } int main() { int n = ri(); std::pair<int, int> pts[n]; for (auto &i : pts) i.first = ri(), i.second = ri(); struct Point { int x; int y; double atan2; }; int res = 0; for (int i = 0; i < n; i++) { std::vector<Point> a; for (int j = 0; j < n; j++) if (i != j) a.push_back({pts[j].first - pts[i].first, pts[j].second - pts[i].second, 0}); for (auto &j : a) j.atan2 = my_atan2(j.x, j.y); for (int j = 0; j + 1 < n; j++) a.push_back(a[j]), a.back().atan2 += 2 * PI; std::sort(a.begin(), a.end(), [] (auto &i, auto &j) { return i.atan2 < j.atan2; }); int head = 0; int64_t r0 = 0, r1 = 0; int cur = 0; for (int j = 0; j + 1 < n; j++) { while (head < 2 * (n - 1) && a[head].atan2 <= a[j].atan2 + PI) r0 += a[head].x, r1 += a[head].y, head++; cur = (cur + (int64_t) r1 * a[j].x - (int64_t) r0 * a[j].y) % MOD; if (cur < 0) cur += MOD; r0 -= a[j].x; r1 -= a[j].y; } res += cur; if (res >= MOD) res -= MOD; } res = (int64_t) res * 333333336 % MOD; printf("%d\n", res); return 0; }