QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#333285#7906. Almost Convexsumi007TL 1ms12232kbC++141.9kb2024-02-19 19:35:142024-02-19 19:35:15

Judging History

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

  • [2024-02-19 19:35:15]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:12232kb
  • [2024-02-19 19:35:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define i64 __int128
#define db double
#define ldb long double
#define ull unsigned long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
#define lowbit(i) (i&-i) 
const int N = 2e5+5;
ll n,top,len,use[N],stk[N],p[N],per[N],rk[N];
struct Node{
    ll x,y;
    friend Node operator - (Node a,Node b){
        return Node{a.x-b.x,a.y-b.y};
    }
    friend Node operator + (Node a,Node b){
        return Node{a.x+b.x,a.y+b.y};
    } 
    friend ll operator * (Node a,Node b){
        return a.x*b.y-a.y*b.x;
    }
}s[N];
double degree(int i,int j){
    return atan2((s[j].y-s[i].y),(s[j].x-s[i].x));
}
bool cmp(Node a,Node b){
    if(a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}
void Andrew(){
    stk[++top] = 1,use[1] = 1;
    for(int i=2;i<=n;i++){
        while(top>1 && (s[stk[top]]-s[stk[top-1]])*(s[i]-s[stk[top]])<0) use[stk[top--]] = 0; 
        stk[++top] = i,use[i] = 1;
    }
    int k = top;
    for(int i=n;i>=1;i--){
        if(use[i]) continue;
        while(top>k && (s[stk[top]]-s[stk[top-1]])*(s[i]-s[stk[top]])<=0) use[stk[top--]] = 0;
        stk[++top] = i,use[i] = 1;
    }
    while(top) p[++len] = stk[top--];
    p[len+1] = p[1];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++) cin >> s[i].x >> s[i].y;
    sort(s+1,s+1+n,cmp);
    Andrew();
    int ans = 1;
    for(int u=1;u<=n;u++){
        if(use[u]) continue;
        int sz = 0;
        for(int i=1;i<=n;i++){
            if(i==u) continue;
            per[++sz] = i;
        }
        sort(per+1,per+1+sz,[&](int x,int y){return degree(u,x)<degree(u,y);});
        for(int i=1;i<=sz;i++) rk[per[i]] = i;
        for(int i=1;i<=len;i++) if(abs(rk[p[i]]-rk[p[i+1]])==1 || abs(rk[p[i]]-rk[p[i+1]])==sz-1) ans++; 
    }
    cout << ans;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 1ms
memory: 12136kb

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

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: