QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#410946#7906. Almost ConvexhuangbrotherWA 12ms4132kbC++171.9kb2024-05-14 18:20:592024-05-14 18:21:00

Judging History

This is the latest submission verdict.

  • [2024-05-14 18:21:00]
  • Judged
  • Verdict: WA
  • Time: 12ms
  • Memory: 4132kb
  • [2024-05-14 18:20:59]
  • Submitted

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'