| ||||||||||
| 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