QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#303182#7906. Almost ConvexqilingTL 1ms4120kbC++142.5kb2024-01-11 20:28:272024-01-11 20:28:28

Judging History

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

  • [2024-01-11 20:28:28]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4120kb
  • [2024-01-11 20:28:27]
  • 提交

answer

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

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];
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;
}

struct node {
    PDD po;
    int idx;
    
    node(PDD po = {0, 0}, int idx = 0) : po(po), idx(idx) {}
    
    node operator - (const node& A) {
        po = po - A.po;
        return *this;
    }
};

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;
    }
    
    andrew();
    
    vector<PDD> v;
    for (int i = 1; i <= n; ++ i) {
        if(!st[i]) v.push_back(q[i]);
    }

    PDD o;
    auto cmp = [&](node a, node b) {
        a = a - o;
        b = b - o;
        if(dcmp(atan2(a.po.y, a.po.x), atan2(b.po.y, b.po.x)) == 0) return a.po.x < b.po.x;
        return dcmp(atan2(a.po.y, a.po.x), atan2(b.po.y, b.po.x)) < 0;
    };
    
    int ans = 1;
    
    vector<node> p;
    for (int i = 0; i < v.size(); ++ i) {
        o = v[i];
        p.clear();
        for (int j = 1; j <= n; ++ j) {
            if(q[j] == o) continue;
            if(st[j]) p.push_back({q[j], 1});
            else p.push_back({q[j], 0});
        }
        sort(p.begin(), p.end(), cmp);
        for (int j = 0; j < p.size() - 1; ++ j) {
            if(p[j].idx && p[j + 1].idx) ++ ans;
        }
        if(p[p.size() - 1].idx && p[0].idx) ++ 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: 4100kb

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

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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: 1ms
memory: 3624kb

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: