QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#710891#7906. Almost ConvexFUCKUCUPWA 7ms3852kbC++202.3kb2024-11-04 22:50:402024-11-04 22:50:41

Judging History

你现在查看的是最新测评结果

  • [2024-11-04 22:50:41]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:3852kb
  • [2024-11-04 22:50:40]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2010;
int T, n, vis[maxn], stk[maxn], top;
struct point { int x, y; };
vector<point> p, convex;
inline point operator - (point p, point q) { return {p.x - q.x, p.y - q.y}; }
inline long long operator * (point p,  point q) { return 1ll * p.x * q.y - 1ll * p.y * q.x; }
inline long long operator ^ (point p,  point q) { return 1ll * p.x * q.x + 1ll * p.y * q.y; }
inline long long len2(point p) { return 1ll * p.x * p.x + 1ll * p.y * p.y; }
inline vector<point> calc_convex(vector<point> &p) {
  vector<point> ans;
  stk[top = 1] = 0;
  for(int i = 1; i < p.size(); ++i) {
    while(top > 1 && (p[stk[top]] - p[stk[top - 1]]) * (p[i] - p[stk[top]]) < 0) --top;
    stk[++top] = i;
  }
//  for(int i = 1; i <= top; ++i) cout << p[stk[i]].x << ' ' << p[stk[i]].y << '\n';
  int cur = top;
  for(int i = (int)p.size() - 2; i >= 0; --i) {
    while(top > cur && (p[stk[top]] - p[stk[top - 1]]) * (p[i] - p[stk[top]]) < 0) --top;
    stk[++top] = i;
  }
  for(int i = 1; i <= top; ++i) ans.push_back(p[stk[i]]), vis[stk[i]] = 1;
//  for(auto [x, y] : ans) cout << x << ',' << y << ' '; cout << "--\n";
  return ans;
}
inline void solve() {
  cin >> n, p = vector<point>(n);
  for(int i = 0; i < n; ++i) cin >> p[i].x >> p[i].y;
  sort(p.begin(), p.end(), [&](auto p, auto q) { return p.x < q.x; });
  for(int i = 0; i < n; ++i) vis[i] = 0;
  convex = calc_convex(p);
//  puts("s");

  int ans = 1;
  for(int i = 0; i < convex.size() - 1; ++i) {
    vector<point> p2;
    for(int j = 0; j < n; ++j) if(!vis[j]) p2.push_back(p[j]);
    sort(p2.begin(), p2.end(), [&](auto a, auto b) {
      long long l1 = len2(a - convex[i]), l2 = len2(b - convex[i]);
      long long m1 = (convex[i + 1] - convex[i]) ^ (a - convex[i]);
      long long m2 = (convex[i + 1] - convex[i]) ^ (b - convex[i]);
      return (__int128)m1 * m1 * l2 > (__int128)m2 * m2 * l1;
    });
//    cout << convex[i].x << ',' << convex[i].y << ' ' << convex[i + 1].x << ',' << convex[i + 1].y << '\n';
//    for(auto [x, y] : p2) cout << x << ',' << y << ' '; cout << '\n';
    point mnp = convex[i + 1];
    for(auto now : p2) if((mnp - convex[i + 1]) * (now - convex[i + 1]) >= 0) ++ans, mnp = now;
  }
  cout << ans << '\n';
}
int main() {
  solve();
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3548kb

input:

7
1 4
4 0
2 3
3 1
3 5
0 0
2 4

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

5
4 0
0 0
2 1
3 3
3 1

output:

5

result:

ok 1 number(s): "5"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

6
0 0
3 0
3 2
0 2
1 1
2 1

output:

7

result:

ok 1 number(s): "7"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

4
0 0
0 3
3 0
3 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: -100
Wrong Answer
time: 7ms
memory: 3544kb

input:

2000
86166 617851
383354 -277127
844986 386868
-577988 453392
-341125 -386775
-543914 -210860
-429613 606701
-343534 893727
841399 339305
446761 -327040
-218558 -907983
787284 361823
950395 287044
-351577 -843823
-198755 138512
-306560 -483261
-487474 -857400
885637 -240518
-297576 603522
-748283 33...

output:

150

result:

wrong answer 1st numbers differ - expected: '718', found: '150'