QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#410946 | #7906. Almost Convex | huangbrother | WA | 12ms | 4132kb | C++17 | 1.9kb | 2024-05-14 18:20:59 | 2024-05-14 18:21:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
const double eps=1e-8;
typedef pair<double ,double >pdd;
int stk[2010],top;
int n;
pdd p[2010];
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-a.y*b.x;
}
double area(pdd a,pdd b,pdd c){
return cross(b-a,c-a);
}
bool use[2010];
void andrew(){
sort(p+1,p+n+1);
for(int i=1;i<=n;i++){
while(top>=2&&area(p[stk[top-1]],p[stk[top]],p[i])>=0)use[stk[top]]=0,top--;
stk[++top]=i;
use[i]=1;
}
use[1]=0;
for(int i=n;i>=1;i--){
if(use[i])continue;
while(top>=2&&area(p[stk[top-1]],p[stk[top]],p[i])>=0)top--;
stk[++top]=i;
use[i]=1;
}
for(int i=1;i<=top;i++)use[stk[i]]=0;
}
pdd c[2010];
double angle(pdd a){
double ans=atan2(a.y,a.x);
// if(ans<0)ans+=2*acos(-1);
return ans;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>p[i].x>>p[i].y;
}
andrew();
// for(int i=1;i<=top;i++)cout<<p[stk[i]].x<<" "<<p[stk[i]].y<<endl;
int ans=1;
// for(int i=1;i<=n;i++)cout<<use[i]<<endl;
for(int i=2;i<=top;i++){
int cnt=0;
for(int j=1;j<=n;j++){
if(!use[j])continue;
double x1=angle(p[stk[i]]-p[stk[i-1]])-angle(p[j]-p[stk[i-1]]);
double x2=angle(p[j]-p[stk[i]])-angle(p[stk[i-1]]-p[stk[i]]);
if(x1<0)x1+=acos(-1);
if(x2<0)x2+=acos(-1);
c[++cnt]={x1,x2};
}
double minn=1e9;
sort(c+1,c+cnt+1);
for(int i=1;i<=cnt;i++){
// cout<<c[i].x<<" "<<c[i].y<<endl;
if(minn<c[i].second);
else ans++;
minn=min(minn,c[i].second);
}
// cout<<ans<<endl;
}
cout<<ans;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4076kb
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: 4040kb
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: 3716kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 4092kb
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: 3648kb
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: 12ms
memory: 4132kb
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:
1053
result:
wrong answer 1st numbers differ - expected: '718', found: '1053'