QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#669361#7906. Almost ConvexCorycle#WA 311ms4196kbC++202.7kb2024-10-23 18:21:092024-10-23 18:21:10

Judging History

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

  • [2024-10-23 18:21:10]
  • 评测
  • 测评结果:WA
  • 用时:311ms
  • 内存:4196kb
  • [2024-10-23 18:21:09]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
ll read(){
    ll s=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){s=s*10+c-'0';c=getchar();}
    return s*f;
}
struct Point{
    ll x,y;
    bool tag;
    Point(ll a=0,ll b=0,bool c=false){
        x=a;y=b;tag=c;
    }
    Point operator-(const Point &b) const{
        return Point(x-b.x,y-b.y,false);
    }
}P[2003];
ll Cross(Point A,Point B,Point C){ //AB x AC
    return (A.x-C.x)*(B.y-C.y)-(A.y-C.y)*(B.x-C.x);
}
ll Dist(Point A,Point B){
    return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);
}
bool cmp(Point A,Point B){
    ll x=Cross(A,B,P[1]);
    if(x>0) return true;
    if(x<0) return false;
    return Dist(A,P[1])<Dist(B,P[1]);
}
int n;
int top,a[2003];
vector<Point> q;
const double eps = 1e-7;
const double pi = acos(-1);
double ang(Point p){
    if(fabs(p.x)<eps){
        if(p.y>0) return pi/2;
        else return 3*pi/2;
    }
    if(fabs(p.y)<eps){
        if(p.x>0) return 0;
        else return pi;
    }
    double res = atan(p.y/(double)p.x);
    if(p.x<0) return res+pi;
    if(p.y<0) return res+2*pi;
    return res;
}
int solve(vector<double> v, double x){
    // cout<<"Solving...\n";
    // cout<<x<<endl;
    // for(auto t:v) cout<<t<<",";
    if(x-v[0]<-eps||x-v[top-1]>eps) return 0;
    if(fabs(x-v[0])<eps||fabs(x-v[top-1])<eps) return -1;
    int l=1,r=top-1,mid,ans;
    while(l<=r){
        mid=(l+r)/2;
        if(v[mid]>=x-eps) r=mid-1,ans=mid;
        else l=mid+1;
    }
    if(fabs(x-v[ans])<eps) return -1;
    return ans;
}
int main(){
    n=read();
    int Minx=inf,Miny=inf,id=0;
    for(int i=1;i<=n;++i){
        P[i].x=read();
        P[i].y=read();
        if(P[i].y<Miny||(P[i].y==Miny&&P[i].x<Minx)){
            Minx=P[i].x;
            Miny=P[i].y;
            id=i;
        }
    }
    swap(P[1],P[id]);
    sort(P+2,P+n+1,cmp);
    a[++top]=1; a[++top]=2;
    for(int i=3;i<=n;++i){
        while(top>=2&&Cross(P[i],P[a[top]],P[a[top-1]])>0) top--;
        a[++top]=i;
    }
    for(int i=1;i<=top;++i) q.push_back(P[a[i]]),P[a[i]].tag=true;
    ll ans = 0;
    for(int i=1;i<=n;++i) if(!P[i].tag){
        set<int> s;
        vector<double> v;
        for(auto p:q) v.push_back(ang(p-P[i]));
        sort(v.begin(),v.end());
        for(int j=1;j<=n;++j) if(!P[j].tag&&i!=j)
            s.insert(solve(v,ang(P[j]-P[i])));
        s.insert(-1);
        // cout<<"S: ";
        // for(auto xx:s) cout<<xx<<" ";
        // cout<<endl;
        // cout<<"P: "<<P[i].x<<" "<<P[i].y<<endl;
        ans += top+1-s.size();
        // cout<<ans<<endl;
    }
    cout<<ans+1;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3988kb

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

input:

4
0 0
0 3
3 0
3 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 311ms
memory: 4196kb

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:

718

result:

ok 1 number(s): "718"

Test #7:

score: 0
Accepted
time: 299ms
memory: 3924kb

input:

2000
571314 -128802
-57762 485216
-713276 485201
-385009 -844644
371507 403789
338703 -272265
-913641 438001
-792118 -481524
709494 213762
-913577 432978
-397111 709021
840950 328210
-843628 452653
-20721 126607
-107804 -338102
930109 -89787
-949115 -76479
-862141 455623
991761 94852
-635475 625573
...

output:

658

result:

ok 1 number(s): "658"

Test #8:

score: 0
Accepted
time: 278ms
memory: 3972kb

input:

2000
-510540 -289561
-602648 -189950
-403224 944455
-369582 -41334
358122 -598933
-817147 470207
-440180 -735160
-705634 61719
319062 897001
-905089 -755682
-408371 -520115
-423336 548115
-590242 835990
208155 883477
-202087 142035
-71545 411206
570690 -673204
-228451 -903435
-732876 -570271
-246755...

output:

309

result:

ok 1 number(s): "309"

Test #9:

score: 0
Accepted
time: 266ms
memory: 3952kb

input:

2000
-532115 566389
138405 49337
398814 -97324
116833 113216
381728 877609
222402 641022
109920 952381
-113880 395181
13780 -572931
-676608 605202
-74328 -503839
-207767 926500
-663270 -146303
197877 280349
275865 -663892
-630214 3286
973786 304855
-493735 841584
394901 -505975
757960 204724
-373328...

output:

239

result:

ok 1 number(s): "239"

Test #10:

score: -100
Wrong Answer
time: 267ms
memory: 3924kb

input:

2000
512636 509804
-661126 -592269
755566 -721837
-878213 441853
-236050 -89069
-181220 155656
203391 691764
940154 260513
747075 373881
620423 840991
-409624 335472
270937 -710659
-751290 -673585
250341 -193243
-250535 618887
-739996 543936
-547741 -213681
-82920 -364319
-611672 737719
930798 46731...

output:

1026

result:

wrong answer 1st numbers differ - expected: '1025', found: '1026'