QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#426610 | #7906. Almost Convex | yuanyq5523 | WA | 377ms | 3788kb | C++17 | 1.6kb | 2024-05-31 16:15:47 | 2024-05-31 16:15:47 |
Judging History
answer
#include <bits/stdc++.h>
#define endl "\n"
#define LL long long
using namespace std;
const int N=2e3+3;
int n,top,ans,rk[N],cur;
bool flag[N];
struct point{LL x,y; int idx;}p[N],s[N],tmp[N],P,O;
point operator+(point a,point b){return point({a.x+b.x,a.y+b.y,0});}
point operator-(point a,point b){return point({a.x-b.x,a.y-b.y,0});}
LL cross(point a,point b,point c){
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
LL cross(point a,point b){return a.x*b.y-b.x*a.y;}
bool cmp1(point A,point B){
LL tmp1=cross(P-O,A-O),tmp2=cross(P-O,B-O);
if ((tmp1>0)!=(tmp2>0)) return tmp1>tmp2;
return cross(A-O,B-O)>0;
}
bool cmp2(point a,point b){
if (a.x==b.x) return a.y<b.y;
else return a.x<b.x;
}
void Andrew(){
sort(p+1,p+n+1,cmp2);
for (int i=1;i<=n;i++){
while (top>1 && cross(s[top-1],s[top],p[i])<=0) top--;
s[++top]=p[i];
}
int t=top;
for (int i=n-1;i>=1;i--){
while (top>t && cross(s[top-1],s[top],p[i])<=0) top--;
s[++top]=p[i];
}
for (int i=1;i<=top;i++){
flag[s[i].idx]=true;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for (int i=1;i<=n;i++){
cin>>p[i].x>>p[i].y;
p[i].idx=i;
}
Andrew();
for (int i=1;i<=n;i++){
if (flag[p[i].idx]) continue;
cur=0;
O=p[i]; P={p[i].x-1,p[i].y,p[i].idx};
for (int j=1;j<=n;j++){
if (p[j].idx==O.idx) continue;
tmp[++cur]=p[j];
}
sort(tmp+1,tmp+cur+1,cmp1);
for (int j=0;j<n-1;j++) rk[tmp[j].idx]=j;
for (int j=1;j<top;j++){
int idx1=s[j].idx;
int idx2=s[j+1].idx;
if ((rk[idx1]+1)%(n-1)==rk[idx2] || (rk[idx2]+1)%(n-1)==rk[idx1]) ans++;
}
}
cout<<ans+1<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3688kb
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: 3680kb
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: 3692kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3684kb
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: 3680kb
input:
4 0 0 0 3 3 0 3 3
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: -100
Wrong Answer
time: 377ms
memory: 3788kb
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:
654
result:
wrong answer 1st numbers differ - expected: '718', found: '654'