Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
WA 求助 QWQ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; typedef pair <double, double> pdd; const int maxn = 100010; int T, n, top, cnt, s[maxn]; vector <int> p; pdd O; pdd a[maxn], b[maxn]; double operator * (pdd A, pdd B) { return A.first * B.second - A.second * B.first; } double dis (pdd x) { return x.first * x.first + x.second * x.second; } pdd emplace (pdd x, pdd y) { return make_pair (y.first - x.first, y.second - x.second); } bool up (pdd x) { return (x.second > 0 || (x.second == 0 && x.first >= 0)); } bool cmp (pdd x, pdd y) { pdd A = emplace (O, x), B = emplace (O, y); if (up (A) != up (B)) return up (A) > up (B); if (A * B != 0) return A * B > 0; return dis (A) < dis (B); } bool cmp1 (int x, int y) { return b[x].second > b[y].second; } bool M (int x, int y, int z) { pdd AB = emplace (a[x], a[y]), BC = emplace (a[y], a[z]); return AB * BC < 0; } int main () { cin.tie (0)->sync_with_stdio (false); cin >> T; while (T--) { cin >> n; O = make_pair (1000000000, 1000000000); for (int i = 1; i <= n; i++) { cin >> b[i].first >> b[i].second; O = min (O, b[i]); } p.clear (); top = cnt = 0; for (int i = 1; i <= n; i++) { if (b[i].first == O.first && b[i] != O) p.push_back (i); else a[++cnt] = b[i]; } if (n < 6) {cout << "NO\n"; continue;} sort (a + 1, a + cnt + 1, cmp); sort (p.begin (), p.end (), cmp1); for (int i = 0; i < p.size (); i++) { a[++cnt] = b[p[i]]; } for (int i = 1; i <= n; i++) { while (top >= 2 && M (top - 1, top, i)) top--; s[++top] = i; } bool ans = true; int sum = 0; for (int i = 1; i <= top && ans; ) { pdd t = emplace (a[s[i]], a[s[i % top + 1]]); if (t * emplace (a[s[i]], a[i % top + 2]) != 0) {ans = false; break;} int j = i; while (j <= top && emplace (a[s[i]], a[s[j % top + 1]]) * t == 0) j++; i = j; sum ++; } if (sum <= 1) cout << "NO\n"; //n点共线 else cout << (ans ? "YES" : "NO") << '\n'; } return 0; } ``` Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator