QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#950147#4132. 逃考Jadonyzx100 ✓144ms12396kbC++148.5kb2025-03-24 20:43:022025-03-24 20:43:10

Judging History

This is the latest submission verdict.

  • [2025-03-24 20:43:10]
  • Judged
  • Verdict: 100
  • Time: 144ms
  • Memory: 12396kb
  • [2025-03-24 20:43:02]
  • Submitted

answer

#include <bits/stdc++.h>
#define eps 1e-10
#define maxn 50005
#define double long double
#define int long long
using namespace std;
struct EDGE{int v,w;};
vector<EDGE>edge[maxn];
int KOP6th_finals;
namespace JiSuanJiHe{
    struct Point{double x,y;};
    double operator *(const Point &C,const Point &NOI){return C.x*NOI.y-C.y*NOI.x;}
    Point operator -(const Point &C,const Point &NOI){return Point{C.x-NOI.x,C.y-NOI.y};}
    Point operator +(const Point &C,const Point &NOI){return Point{C.x+NOI.x,C.y+NOI.y};}
    bool operator ==(const Point &C,const Point &D){return C.x==D.x&&C.y==D.y;}
    inline bool cmp(Point C,Point NOI){
        if(C.x!=NOI.x)return C.x<NOI.x;
        return C.y<NOI.y;
    }
    inline bool left(Point C,Point A,Point B){return (B-A)*(C-B)>=0;}
    inline bool right(Point C,Point A,Point B){return (B-A)*(C-B)<=0;}
    inline bool online(Point C,Point A,Point B){return !(right(C,A,B)||left(C,A,B));}
    inline double pf(double x){return x*x;}
    inline double dis(Point xx,Point yy){return sqrt(pf(xx.x-yy.x)+pf(xx.y-yy.y));}
    Point a[maxn],stk[maxn];
    inline void TuBao(int &n){
        int top=0,res=1;
        sort(a+1,a+1+n,cmp);
        stk[++top]=a[1];
        for(int i=2;i<=n;++i){
            while(top>=2&&right(a[i],stk[top-1],stk[top]))top--;
            stk[++top]=a[i];
        }
        for(int i=n-1;i>=1;--i){
            while(res>=2&&right(a[i],stk[top-1],stk[top]))top--,res--;
            stk[++top]=a[i];++res;
        }
        n=top-1;
        for(int i=1;i<=n;++i)a[i]=stk[i];
        return;
    }
    struct Line{double A,B,C;};
    inline Point jiao(Line A,Line B){
        if(A.A==0&&B.B==0){return Point{-B.C/B.A,-A.C/A.B};}
        else if(A.B==0&&B.A==0){return Point{-A.C/A.A,-B.C/B.B};}
        if(B.A==0||B.B==0)swap(A,B);
        if(A.A==0){
            double y=-A.C/A.B;
            double x=(-B.C-B.B*y)/B.A;
            return Point{x,y};
        }
        if(A.B==0){
            double x=-A.C/A.A;
            double y=(-B.C-B.A*x)/B.B;
            return Point{x,y};
        }
        A.B/=A.A;A.C/=A.A;A.A=1;
        B.B/=B.A;B.C/=B.A;B.A=1;
        double y=((B.C-A.C)/(A.B-B.B));
        double x=-(B.C+B.B*y)/B.A;
        return Point{x,y};
    }
    inline double dis(Point A,Line line){return fabs(A.x*line.A+A.y*line.B+line.C)/(sqrt(pf(line.A)+pf(line.B)));}
    inline double dis(Line line,Point A){return fabs(A.x*line.A+A.y*line.B+line.C)/(sqrt(pf(line.A)+pf(line.B)));}
    inline double k(Point A,Point B){return (A.y-B.y)/(A.x-B.x);}
    inline Line makeline(Point A,Point B){
        Line ans;
        if(A.x==B.x){ans.A=1;ans.B=0;ans.C=-A.x;}
        else if(A.y==B.y){ans.A=0;ans.B=1;ans.C=-A.y;}
        else{ans.A=k(A,B);ans.B=-1;ans.C=-(ans.A*A.x+ans.B*A.y);}
        return ans;
    }
    inline Line makeline(Point p,double A,double B){
        Line ANS;ANS.A=A;ANS.B=B;ANS.C=-(p.x*A+p.y*B);
        return ANS;
    }
    inline Line make_zhong_chui(Point A,Point B){
        Line czr=makeline(A,B);
        Line ans;ans.A=-czr.B;ans.B=czr.A;
        Point mid={(A.x+B.x)*0.5,(A.y+B.y)*0.5};
        ans.C=-(mid.x*ans.A+mid.y*ans.B);
        return ans;
    }
    int now,total;
    inline int update(int noi=now){
        int czr=noi+1;
        if(czr>total)czr=1;
        return czr;
    }
    inline void fix_(Point &A){
        if(A.x<=eps&&A.x>=-eps)A.x=+0.000;
        if(A.y<=eps&&A.y>=-eps)A.y=+0.000;
        return;
    }
    int vecnt=0;
    struct Vector{Point st,ed;double theta;int id;}vec[maxn];
    inline bool cmp111(Vector aaa,Vector bbb){
        if(fabs(aaa.theta-bbb.theta)>eps)return aaa.theta<bbb.theta;
        return left(aaa.ed,bbb.st,bbb.ed);
    }
    inline double angle(Vector aaa){return atan2(aaa.ed.y-aaa.st.y,aaa.ed.x-aaa.st.x);}
    inline double angle(Point aaa){return atan2(aaa.y,aaa.x);}
    inline double S(){
        double ans=0;
        for(int i=1;i<=total;++i)
            ans+=a[i]*a[update(i)];
        return ans/2;
    }
    deque<Vector>q;
    inline void Half_Pure_Memory_Foot(){
        sort(vec+1,vec+1+vecnt,cmp111);
        for(int i=1;i<=vecnt;++i){
            Point ccf=vec[i].st-vec[i].ed,ioi=vec[i-1].st-vec[i-1].ed;
            if(fabs(angle(ccf)-angle(ioi))<=eps)continue;
            Point noi=vec[i].ed-vec[i].st;
            while(q.size()>=2){
                bool f=0;
                Point Jiao=jiao(makeline(q[q.size()-1].st,q[q.size()-1].ed),makeline(q[q.size()-2].st,q[q.size()-2].ed));
                f=right(Jiao,vec[i].st,vec[i].ed);
                if(!f)break;
                q.pop_back();
            }
            while(q.size()>=2){
                bool f=0;
                Point Jiao=jiao(makeline(q[0].st,q[0].ed),makeline(q[1].st,q[1].ed));
                f=right(Jiao,vec[i].st,vec[i].ed);
                if(!f)break;
                q.pop_front();
            }
            q.push_back(vec[i]);
        }
        while(q.size()>2){
            bool f=0;
            Point Jiao=jiao(makeline(q[q.size()-1].st,q[q.size()-1].ed),makeline(q[q.size()-2].st,q[q.size()-2].ed));
            f=right(Jiao,q[0].st,q[0].ed);
            if(!f)break;
            q.pop_back();
        }
        while(q.size()>2){
            bool f=0;
            Point Jiao=jiao(makeline(q[1].st,q[1].ed),makeline(q[0].st,q[0].ed));
            f=right(Jiao,q[q.size()-1].st,q[q.size()-1].ed);
            if(!f)break;
            q.pop_front();
        }
        int noi=q.size();total=0;
    }
}
using namespace JiSuanJiHe;
inline void insert(double A,double B,double C,int id){
    Point aaa={-C/(pf(A)+pf(B))*A,-C/(pf(A)+pf(B))*B};
    Point bbb={-C/(pf(A)+pf(B))*A+B,-C/(pf(A)+pf(B))*B-A};
    vec[++vecnt]={aaa,bbb,angle(bbb-aaa),id};
}
int n;Point ak[maxn],val[maxn];
map<pair<double,double>,int>mp;
int T,startpoint=0;
double X1,Y1,X0,Y0;
inline void init(){
    for(int i=0;i<=n+1;++i)edge[i].clear();
    mp.clear();
    return;
}
int Dis[maxn];
bool in[maxn];
Vector fjx[5];
inline void solve(){
    init();
    cin>>n>>X1>>Y1>>X0>>Y0;
    init();
    Point AAA={0,0};
    Point BBB={X1,0};
    Point CCC={X1,Y1};
    Point DDD={0,Y1};
    fjx[1]={AAA,BBB,angle(BBB-AAA),n+1};
    fjx[2]={BBB,CCC,angle(CCC-BBB),n+1};
    fjx[3]={CCC,DDD,angle(DDD-CCC),n+1};
    fjx[4]={DDD,AAA,angle(AAA-DDD),n+1};
    double mindis=1e18;Point xm={X0,Y0};
    for(int i=1;i<=n;++i){
        cin>>ak[i].x>>ak[i].y;
        in[i]=1;++mp[make_pair(ak[i].x,ak[i].y)];
        // cerr<<mp[make_pair(ak[i].x,ak[i].y)]<<" ";
        if(ak[i].x<0||ak[i].y<0||ak[i].x>X1||ak[i].y>Y1)
            in[i]=0;
    }
    if(n==0){cout<<0<<"\n";return;}
    for(int i=1;i<=n;++i)mindis=min(mindis,dis(xm,ak[i]));
    for(int i=1;i<=n;++i)if(dis(xm,ak[i])==mindis)edge[startpoint].push_back({i,1});
    for(int i=1;i<=n;++i){
        if(!in[i])continue;
        vecnt=0;
        for(int j=1;j<=n;++j){
            if(i==j||(!in[j]))continue;
            insert(2*ak[i].x-2*ak[j].x,2*ak[i].y-2*ak[j].y,pf(ak[j].x)+pf(ak[j].y)-pf(ak[i].x)-pf(ak[i].y),j);
        }
        for(int j=1;j<=4;++j)vec[++vecnt]=fjx[j];
        Half_Pure_Memory_Foot();
        if(q.size()>=2){
            Vector PRE;
            while(q.size()){
                auto now=q.front();q.pop_front();
                if(now.id==n+1){
                    auto nxt=q[0];
                    auto ccf=jiao(makeline(nxt.st,nxt.ed),makeline(PRE.st,PRE.ed));
                    auto CCF=makeline(now.st,now.ed);
                    int val=0;
                    if(ccf.x*CCF.A+ccf.y*CCF.B+CCF.C==0)val=2;
                    edge[i].push_back({now.id,val});
                }
                else edge[i].push_back({now.id,mp[make_pair(ak[now.id].x,ak[now.id].y)]});
                PRE=now;
            }
        }
        while(q.size())q.pop_front();
    }
    for(int i=1;i<=n+1;++i)Dis[i]=1e18;Dis[0]=0;
    priority_queue<pair<int,int>>Q;Q.push(make_pair(0,0));
    while(Q.size()){
        auto now=Q.top();Q.pop();
        for(auto E:edge[now.second]){
            int v=E.v,w=E.w;
            if(Dis[v]>Dis[now.second]+w){
                Dis[v]=Dis[now.second]+w;
                Q.push(make_pair(-Dis[v],v));
            }
        }
    }
    // for(int i=0;i<=n;++i){
    //     for(auto v:edge[i]){
    //         cerr<<i<<" "<<v.v<<" "<<v.w<<"\n";
    //     }
    // }
    cout<<Dis[n+1]<<"\n";
    return;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>T;while(T--)solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 0ms
memory: 12396kb

input:

2
0
10 10 5 5
3
3 3 2 2
1 1
2 2
2 1

output:

0
1

result:

ok 2 lines

Test #2:

score: 10
Accepted
time: 0ms
memory: 12340kb

input:

1
67
9435 9681 4721 4843
5185 4697
5653 4554
6121 4411
6589 4268
7057 4125
7525 3982
7993 3839
8461 3696
8929 3553
9397 3410
4597 5435
4477 6030
4357 6625
4237 7220
4117 7815
3997 8410
3877 9005
3757 9600
5142 5421
5567 6002
5992 6583
6417 7164
6842 7745
7267 8326
7692 8907
8117 9488
5537 4936
6357 ...

output:

6

result:

ok single line: '6'

Test #3:

score: 10
Accepted
time: 3ms
memory: 10360kb

input:

3
36
9745 9171 4873 4580
4167 4700
3462 4815
2757 4930
2052 5045
1347 5160
642 5275
5766 4918
6660 5251
7554 5584
8448 5917
9342 6250
4320 4536
3768 4487
3216 4438
2664 4389
2112 4340
1560 4291
1008 4242
456 4193
4587 4780
4302 4975
4017 5170
3732 5365
3447 5560
3162 5755
2877 5950
2592 6145
2307 63...

output:

2
2
4

result:

ok 3 lines

Test #4:

score: 10
Accepted
time: 21ms
memory: 11288kb

input:

1
253
9369 9873 4680 4934
4874 5121
5064 5306
5254 5491
5444 5676
5634 5861
5824 6046
6014 6231
6204 6416
6394 6601
6584 6786
6774 6971
6964 7156
7154 7341
7344 7526
7534 7711
7724 7896
7914 8081
8104 8266
8294 8451
8484 8636
8674 8821
8864 9006
9054 9191
9244 9376
4451 5217
4218 5498
3985 5779
3752...

output:

7

result:

ok single line: '7'

Test #5:

score: 10
Accepted
time: 13ms
memory: 10520kb

input:

2
142
9306 9315 4650 4648
8460 4514
7543 6239
6060 1411
6951 5194
6337 4448
3700 8678
412 8483
4579 8598
1660 4373
7813 5263
7878 7782
3376 383
6608 3375
1208 7523
279 9148
1402 2080
59 5554
6680 7253
7202 286
918 8348
7634 1758
554 2314
8253 8983
7130 336
2367 3996
9070 1377
4372 4574
2140 4554
144...

output:

4
4

result:

ok 2 lines

Test #6:

score: 10
Accepted
time: 22ms
memory: 12248kb

input:

2
182
1548 9698 770 4842
1540 6653
860 7475
98 5098
984 8531
372 9148
249 1813
875 8382
1453 2470
1464 3608
1497 8459
965 2261
1464 4740
1296 3144
974 9366
510 5482
1180 5674
1169 4362
811 7700
300 2825
481 9388
276 5373
83 1545
975 6777
284 3019
882 2127
1495 1847
401 1588
942 1956
721 7587
68 5616...

output:

2
4

result:

ok 2 lines

Test #7:

score: 10
Accepted
time: 118ms
memory: 11404kb

input:

3
64
9428 9393 4711 4691
5175 4610
5636 4524
6097 4438
6558 4352
7019 4266
7480 4180
7941 4094
8402 4008
8863 3922
9324 3836
4313 3892
3912 3088
3511 2284
3110 1480
2709 676
4287 5109
3860 5522
3433 5935
3006 6348
2579 6761
2152 7174
1725 7587
1298 8000
871 8413
444 8826
17 9239
3916 4411
3118 4126
...

output:

6
23
21

result:

ok 3 lines

Test #8:

score: 10
Accepted
time: 121ms
memory: 11408kb

input:

3
46
9613 9894 4800 4938
4308 2877
6282 5007
4901 7579
3871 1414
2182 9338
8619 1518
2697 2588
5338 862
9379 2341
2032 4238
723 1294
1807 2771
316 8365
2903 8683
6249 1985
2044 7215
6709 2717
4466 6965
260 232
7092 5396
2004 7846
8023 8119
6567 663
2687 2195
1376 3131
4529 1643
5548 7805
9083 2318
8...

output:

2
19
13

result:

ok 3 lines

Test #9:

score: 10
Accepted
time: 141ms
memory: 10640kb

input:

3
38
9558 9625 4782 4807
5085 4701
5391 4590
5697 4479
6003 4368
6309 4257
6615 4146
6921 4035
7227 3924
7533 3813
7839 3702
8145 3591
8451 3480
8757 3369
9063 3258
9369 3147
4526 5234
4273 5656
4020 6078
3767 6500
3514 6922
3261 7344
3008 7766
2755 8188
2502 8610
2249 9032
1996 9454
4948 3929
5117 ...

output:

2
13
16

result:

ok 3 lines

Test #10:

score: 10
Accepted
time: 144ms
memory: 10564kb

input:

3
109
9264 9189 4633 4592
4081 4407
3530 4220
2979 4033
2428 3846
1877 3659
1326 3472
775 3285
224 3098
4830 4304
5028 4014
5226 3724
5424 3434
5622 3144
5820 2854
6018 2564
6216 2274
6414 1984
6612 1694
6810 1404
7008 1114
7206 824
7404 534
7602 244
4286 4486
3940 4378
3594 4270
3248 4162
2902 4054...

output:

6
9
10

result:

ok 3 lines