QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#303017#7906. Almost ConvexqilingTL 1ms4224kbC++142.4kb2024-01-11 16:53:172024-01-11 16:53:17

Judging History

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

  • [2024-01-11 16:53:17]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4224kb
  • [2024-01-11 16:53:17]
  • 提交

answer

#include <map>
#include <cmath>
#include <iostream>
#include <algorithm>

using namespace std;

#define N 2010
#define eps 1e-8
#define x first
#define y second
#define endl '\n'
#define PDD pair<double, double>

int n;
PDD q[N], q1[N];
int stk[N], top;
bool st[N];

PDD operator- (PDD a, PDD b) { return {a.x - b.x, a.y - b.y};}
double cross (PDD a, PDD b) { return a.x * b.y - b.x * a.y;}
double area (PDD a, PDD b, PDD c) { return cross(b - a, c - a);}

void andrew() {
    sort(q + 1, q + n + 1);
    
    for (int i = 1; i <= n; ++ i) {
        while(top >= 2 && area(q[stk[top - 1]], q[stk[top]], q[i]) <= 0) {
            if(area(q[stk[top - 1]], q[stk[top]], q[i]) < 0) st[stk[top --]] = false;
            else top --;
        }
        stk[++ top] = i;
        st[i] = true;
    }
    
    st[1] = false;
    for (int i = n; i >= 1; -- i) {
        if(st[i]) continue;
        while(top >= 2 && area(q[stk[top - 1]], q[stk[top]], q[i]) <= 0) {
            if(area(q[stk[top - 1]], q[stk[top]], q[i]) < 0) st[stk[top --]] = false;
            else top --;
        }
        stk[++ top] = i;
        st[i] = true;
    }
}

int dcmp(double a, double b) {
    if(fabs(a - b) < eps) return 0;
    if(a < b) return -1;
    return 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
        cin >> q[i].x >> q[i].y;
        q1[i] = q[i];
    }
    
    andrew();
    map<PDD, PDD> l, r;
    stk[0] = stk[top - 1];
    for (int i = 1; i < top; ++ i) {
        l[q[stk[i]]] = q[stk[i - 1]];
        r[q[stk[i]]] = q[stk[i + 1]];
    }
    int ans = 1;
    PDD o;
    auto cmp = [&](PDD a, PDD b) {
        a = a - o;
        b = b - o;
        if(dcmp(atan2(a.y, a.x), atan2(b.y, b.x)) == 0) return a.x < b.x;
        return dcmp(atan2(a.y, a.x), atan2(b.y, b.x)) < 0;
    };
    for (int i = 1; i <= n; ++ i) {
        if(st[i]) continue;
        o = q[i];
        for (int j = 1; j <= n; ++ j) {
            q1[j] = q[j];
        }
        swap(q1[1], q1[i]);
        sort(q1 + 2, q1 + n + 1, cmp);
        for (int j = 2; j < n; ++ j) {
            if((r[q1[j]] == q1[j + 1] && q1[j]== l[q1[j + 1]]) ||
               (l[q1[j]] == q1[j + 1] && q1[j] == r[q1[j + 1]])) {
                ++ ans;
            }
        }
        if(r[q1[n]] == q1[2] && q1[n] == l[q1[2]]) {
            ++ ans;
        }
    }
    cout << ans << endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4224kb

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

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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

input:

4
0 0
0 3
3 0
3 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: -100
Time Limit Exceeded

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: