Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

WA 求助 QWQ

Posted by yanquan at 2024-01-30 09:46:32 on Problem 1228
```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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator