QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#333285 | #7906. Almost Convex | sumi007 | TL | 1ms | 12232kb | C++14 | 1.9kb | 2024-02-19 19:35:14 | 2024-02-19 19:35:15 |
Judging History
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...