QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#332976#7906. Almost ConvexlhzawaRE 0ms4356kbC++141.6kb2024-02-19 16:44:012024-02-19 16:44:01

Judging History

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

  • [2024-02-19 16:44:01]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:4356kb
  • [2024-02-19 16:44:01]
  • 提交

answer

#include<bits/stdc++.h>
const int maxn = 2e3 + 10;
int dx[maxn], dy[maxn];
int P[maxn], m, P_[maxn], m_;
double r[maxn];
int p[maxn];
bool vis[maxn];
struct R {double r1, r2;} _[maxn];
int main() {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d%d", &dx[i], &dy[i]);
    int sid = 1, mxx = -1e9;
    for (int i = 2; i <= n; i++) dx[i] < dx[sid] && (sid = i), mxx = std::max(mxx, dx[i]);
    P[++m] = sid;
    while (dx[P[m]] != mxx) {
        for (int i = 1; i <= n; i++) r[i] = atan2(dy[i] - dy[P[m]], dx[i] - dx[P[m]]);
        int nxt = P[m] == 1 ? 2 : 1;
        for (int i = 1; i <= n; i++) i != P[m] && r[i] < r[nxt] && (nxt = i);
        P[++m] = nxt;
    }
    P_[++m_] = sid;
    while (dx[P_[m_]] != mxx) {
        for (int i = 1; i <= n; i++) r[i] = atan2(dy[i] - dy[P_[m_]], dx[i] - dx[P_[m_]]);
        int nxt = P_[m_] == 1 ? 2 : 1;
        for (int i = 1; i <= n; i++) i != P_[m_] && r[i] > r[nxt] && (nxt = i);
        P_[++m_] = nxt;
    }
    if (P_[m_] == P[m]) m_--;
    while (m_) P[++m] = P_[m_--];
    for (int i = 1; i <= m; i++) vis[P[i]] = 1; 
    int cnt = 1;
    for (int i = 2; i <= m; i++) {
        int K = 0;
        for (int j = 1; j <= n; j++) ! vis[j] && (_[++K] = {atan2(dy[j] - dy[P[i]], dx[j] - dx[P[i]]), atan2(dy[j] - dy[P[i - 1]], dx[j] - dx[P[i - 1]])}, 1);
        if (! K) continue;
        std::stable_sort(_ + 1, _ + K + 1, [&](const R &x, const R &y) {return x.r1 > y.r1;});
        cnt++;
        double mn = _[1].r2;
        for (int j = 2; j <= K; j++) _[j].r2 < mn && (cnt++, mn = _[j].r2, 1);
    }
    printf("%d\n", cnt);
    return 0;
}

详细

Test #1:

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

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: 4180kb

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: 4172kb

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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: 4272kb

input:

4
0 0
0 3
3 0
3 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: -100
Runtime Error

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:


result: