QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#806893#6799. Road ConstructionWuyanruAC ✓2ms4764kbC++146.8kb2024-12-09 16:34:242024-12-09 16:34:25

Judging History

This is the latest submission verdict.

  • [2024-12-09 16:34:25]
  • Judged
  • Verdict: AC
  • Time: 2ms
  • Memory: 4764kb
  • [2024-12-09 16:34:24]
  • Submitted

answer

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
struct node
{
    int x,y;
    int id;
}a[10001];
int ty[10001];
vc<int>v1[10001],v2[10001];
int x[10001],y[10001];
int num1[10001],c1;
int num2[10001],c2;
vc<pi>ans1,ans2;
int n,m,c;
inline ll X(int p,int q){ return x[q]-x[p];}
inline ll Y(int p,int q){ return y[q]-y[p];}
inline ll cha(int a,int b,int c)
{
    return X(a,b)*Y(a,c)-X(a,c)*Y(a,b);
}
inline void init()
{
    //左上->右下凸壳
    sort(a+1,a+c+1,[](node a,node b){ return a.x==b.x?a.y>b.y:a.x<b.x;});
    for(int i=1;i<=c;i++)
    {
        int u=a[i].id;
        while(c1>=2)
        {
            int p=num1[c1-1],q=num1[c1];
            if(Y(p,q)*X(q,u)<Y(q,u)*X(p,q)) c1--;
            else break;
        }
        num1[++c1]=u;
    }
    //右下->左上凸壳
    sort(a+1,a+c+1,[](node a,node b){ return a.x==b.x?a.y<b.y:a.x>b.x;});
    for(int i=1;i<=c;i++)
    {
        int u=a[i].id;
        while(c2>=2)
        {
            int p=num2[c2-1],q=num2[c2];
            if(Y(p,q)*X(q,u)<Y(q,u)*X(p,q)) c2--;
            else break;
        }
        num2[++c2]=u;
    }

    // for(int i=1;i<=c1;i++) printf("%d%c",num1[i]," \n"[i==c1]);
    // for(int i=1;i<=c2;i++) printf("%d%c",num2[i]," \n"[i==c2]);
}
inline void push(int x,int y)
{
    if(x<=n) ans1.push_back(pi(x,y));
    else ans2.push_back(pi(x-n,y-n));
}
inline bool ro(int A,int B,int C){ return cha(A,B,C)>0;}
inline bool tri(int A,int B,int C,int p)
{
    bool f=1;
    if(ro(A,B,p)==ro(A,C,p)) f=0;
    if(ro(B,A,p)==ro(B,C,p)) f=0;
    if(ro(C,A,p)==ro(C,B,p)) f=0;
    return f;
}
inline void run(int A,int B,int C,vc<int>sa,vc<int>sb)
{
    if(sa.size())
    {
        int p=sa[0];push(A,p);
        vc<int>v1,v2,v3,v4,v5,v6;
        for(int q:sa) if(q!=p)
        {
            if(tri(A,B,p,q)) v1.push_back(q);
            else if(tri(A,C,p,q)) v3.push_back(q);
            else v5.push_back(q);
        }
        for(int q:sb)
        {
            if(tri(A,B,p,q)) v2.push_back(q);
            else if(tri(A,C,p,q)) v4.push_back(q);
            else v6.push_back(q);
        }
        run(B,A,p,v2,v1);
        run(C,A,p,v4,v3);
        run(p,B,C,v5,v6);
    }
    else
    {
        for(int i:sb) push(B,i);
    }
}
inline bool checkc(int p)
{
    for(int i=1;i<c1;i++) if(p==num1[i]) return true;
    for(int i=1;i<c2;i++) if(p==num2[i]) return true;
    return false;
}
inline int get(int p,int id)
{
    if(checkc(p)) return -1;
    for(int i=1;i<c1;i++) if(tri(num1[i],num1[i+1],id,p)) return num1[i];
    for(int i=1;i<c2;i++) if(tri(num2[i],num2[i+1],id,p)) return num2[i];
    assert(0);return 114514;
}
inline int wtf(int p,int id,vc<int>&nod1,vc<int>&nod2)
{
    for(unsigned i=1;i<nod1.size();i++) if(tri(nod1[i-1],nod1[i],id,p)) return nod1[i-1];
    if(tri(nod1.back(),nod2[0],id,p)) return nod1.back();
    return nod2[0];
}
inline void run(vc<int>nod1,vc<int>nod2,int f3,int s)
{
    if(f3==-1)
    {
        for(int i=1;i<=c;i++) if(ty[i]==s) push(nod1[0],i);
    }
    else
    {
        // printf("f3=%d\n",f3);
        push(f3,nod2[0]);
        for(int i=1;i<=c;i++) if(ty[i]==s&&i!=f3)
        {
            int f=wtf(i,f3,nod1,nod2);
            if((i<=n)==(f3<=n)) v1[f].push_back(i);
            else v2[f].push_back(i);
            // printf("i=%d : f=%d\n",i,f);
        }
        for(unsigned i=1;i<nod1.size();i++)
        {
            run(f3,nod1[i-1],nod1[i],v1[nod1[i-1]],v2[nod1[i-1]]);
            v1[nod1[i-1]].clear(),v2[nod1[i-1]].clear();
        }
        run(nod1.back(),f3,nod2[0],v2[nod1.back()],v1[nod1.back()]);
        v2[nod1.back()].clear(),v2[nod1.back()].clear();
        run(nod1[0],f3,nod2[0],v2[nod2[0]],v1[nod2[0]]);
        v2[nod2[0]].clear(),v1[nod2[0]].clear();
    }
}
int main()
{
    n=read(),m=read();c=n+m;
    for(int i=1;i<=c;i++) a[i].x=x[i]=read(),a[i].y=y[i]=read(),a[i].id=i;

    init();

    int cnt=0;vc<int>nod1,nod2;
    for(int i=1;i<c1;i++)
    {
        if(cnt) num1[i]<=n?nod1.push_back(num1[i]):nod2.push_back(num1[i]);
        cnt+=(num1[i]<=n)!=(num1[i+1]<=n);
    }
    for(int i=1;i<c2;i++)
    {
        if(cnt) num2[i]<=n?nod1.push_back(num2[i]):nod2.push_back(num2[i]);
        cnt+=(num2[i]<=n)!=(num2[i+1]<=n);
    }
    // if(c==100) cout<<cnt<<endl;
    if(cnt>2)
    {
        printf("Impossible\n");
        return 0;
    }
    if(!cnt)
    {
        //先把外围连起来
        for(int i=1;i<c1;i++) push(num1[i],num1[i+1]);
        for(int i=2;i<c2;i++) push(num2[i],num2[i+1]);
        int id=num1[1]<=n?n+1:1;
        for(int i=1;i<=c;i++) if(i!=id)
        {
            int f=get(i,id);if(f==-1) continue;
            if((i<=n)==(id<=n)) v1[f].push_back(i);
            else v2[f].push_back(i);
        }
        for(int i=1;i<c1;i++) run(id,num1[i],num1[i+1],v1[num1[i]],v2[num1[i]]);
        for(int i=1;i<c2;i++) run(id,num2[i],num2[i+1],v1[num2[i]],v2[num2[i]]);
    }
    else
    {
        cnt=0;
        for(int i=1;i<c1;i++)
        {
            if(!cnt) num1[i]<=n?nod1.push_back(num1[i]):nod2.push_back(num1[i]);
            cnt+=(num1[i]<=n)!=(num1[i+1]<=n);
        }
        for(int i=1;i<c2;i++)
        {
            if(!cnt) num2[i]<=n?nod1.push_back(num2[i]):nod2.push_back(num2[i]);
            cnt+=(num2[i]<=n)!=(num2[i+1]<=n);
        }

        // for(int i:nod1) printf("%d ",i);;putchar('\n');
        // for(int i:nod2) printf("%d ",i);;putchar('\n');

        int f1=nod1[0],f2=nod2[0],f3=-1,f4=-1;
        for(unsigned i=1;i<nod1.size();i++) push(nod1[i-1],nod1[i]);
        for(unsigned i=1;i<nod2.size();i++) push(nod2[i-1],nod2[i]);
        
        for(int i=1;i<=c;i++) if(!checkc(i))
        {
            if(cha(f1,f2,i)>0)
            {
                ty[i]=1;
                if(i>n) f3=i;
            }
            else
            {
                ty[i]=2;
                if(i<=n) f4=i;
            }
            // printf("i=%d ty=%d\n",i,ty[i]);
        }
        run(nod1,nod2,f3,1);
        run(nod2,nod1,f4,2);
    }

    // putchar('\n');
    for(auto i:ans1) printf("%d %d\n",i.first,i.second);
    // putchar('\n');
    for(auto i:ans2) printf("%d %d\n",i.first,i.second);
    return 0;
}
/*
4 5
0 0
0 4
4 6
6 2
8 4
8 0
3 2
4 3
5 1
*/

詳細信息

Test #1:

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

input:

2 3
0 0
1 1
1 0
0 1
2 3

output:

2 1
2 3
3 1

result:

ok AC

Test #2:

score: 0
Accepted
time: 1ms
memory: 4440kb

input:

500 500
207579012 1361955
376140462 628145516
186969585 883515280
326402539 762888635
158176572 98152102
9580638 127860889
646139319 570870044
484027666 178509022
841082555 61263304
940563715 558212774
496147999 579113528
837151740 925801172
285845005 656585275
403573723 902071050
9467290 727123762
...

output:

Impossible

result:

ok AC

Test #3:

score: 0
Accepted
time: 1ms
memory: 4260kb

input:

5 5
207579012 1361955
186969585 883515280
9580638 127860889
646139319 570870044
841082555 61263304
940563715 558212774
376140462 628145516
326402539 762888635
158176572 98152102
484027666 178509022

output:

5 1
1 3
3 2
2 4
5 1
5 4
5 2
2 3

result:

ok AC

Test #4:

score: 0
Accepted
time: 1ms
memory: 4536kb

input:

7 3
207579012 1361955
186969585 883515280
326402539 762888635
9580638 127860889
646139319 570870044
841082555 61263304
940563715 558212774
376140462 628145516
158176572 98152102
484027666 178509022

output:

4 2
2 7
6 1
1 4
2 3
7 5
1 3
1 2

result:

ok AC

Test #5:

score: 0
Accepted
time: 1ms
memory: 4548kb

input:

4 6
376140462 628145516
326402539 762888635
158176572 98152102
646139319 570870044
207579012 1361955
186969585 883515280
9580638 127860889
484027666 178509022
841082555 61263304
940563715 558212774

output:

1 2
1 4
1 3
3 2
2 6
5 1
1 3
5 4

result:

ok AC

Test #6:

score: 0
Accepted
time: 1ms
memory: 4312kb

input:

67 33
376140462 628145516
326402539 762888635
646139319 570870044
940563715 558212774
496147999 579113528
837151740 925801172
403573723 902071050
520690249 899374333
491747709 798571510
643215695 799313372
614608448 789204466
806956091 555253431
300206284 785986538
775142614 732553407
457641318 5551...

output:

59 38
38 46
46 36
36 32
32 67
59 3
59 4
59 5
59 6
59 7
59 8
59 9
59 10
59 11
59 12
59 14
59 16
59 17
59 18
59 19
59 20
59 21
59 22
59 23
59 24
59 25
59 26
59 27
59 28
59 29
59 30
59 31
59 33
59 34
59 37
59 39
59 40
59 41
59 42
59 43
59 45
59 48
59 50
59 52
59 55
59 62
59 63
59 64
66 59
59 47
59 54
5...

result:

ok AC

Test #7:

score: 0
Accepted
time: 2ms
memory: 4464kb

input:

2069 931
376140462 628145516
326402539 762888635
646139319 570870044
940563715 558212774
496147999 579113528
837151740 925801172
403573723 902071050
520690249 899374333
491747709 798571510
643215695 799313372
614608448 789204466
806956091 555253431
300206284 785986538
775142614 732553407
457641318 5...

output:

1489 1680
1680 1973
1973 1812
1812 996
996 882
882 1358
1358 909
909 591
591 958
958 1278
1278 1231
1231 1790
1790 1874
1874 1741
1741 1867
1867 2012
1680 1408
1680 1667
1680 1517
1680 1569
1680 1613
1680 1683
1680 1702
1680 1792
1680 1872
1680 1890
1680 1500
1680 1661
1680 1789
1680 1905
1680 2004
...

result:

ok AC

Test #8:

score: 0
Accepted
time: 1ms
memory: 4608kb

input:

462 538
207579012 1361955
376140462 628145516
9580638 127860889
484027666 178509022
285845005 656585275
9467290 727123762
806956091 555253431
158398859 751354013
205461189 882264704
300206284 785986538
775142614 732553407
896205950 132099860
506507263 590064713
904237001 706091347
644505508 89616246...

output:

85 1
1 149
149 181
85 295
1 86
1 391
1 292
86 175
85 48
85 144
48 281
48 371
48 384
1 163
1 314
85 95
85 298
149 49
149 370
49 271
85 147
462 85
462 3
462 33
462 461
33 139
33 54
462 277
277 372
462 105
105 276
3 64
3 66
64 249
462 4
462 303
462 389
303 318
303 362
318 378
4 53
4 425
4 361
53 161
4 ...

result:

ok AC

Test #9:

score: 0
Accepted
time: 2ms
memory: 4764kb

input:

1491 1509
376140462 628145516
158176572 98152102
940563715 558212774
403573723 902071050
631265400 296231662
158398859 751354013
205461189 882264704
896205950 132099860
210461042 793692316
537850352 901329638
614794871 29523791
905203769 570497239
337246324 118054686
644505508 896162463
122173997 59...

output:

743 213
213 619
619 1296
1296 920
920 1096
1096 972
972 1449
1449 994
994 624
624 1055
1055 1370
1370 1321
865 1073
1073 755
755 1057
1057 1383
1383 909
909 1255
1255 164
164 1029
1029 111
111 1308
1308 743
743 178
178 895
743 547
743 839
178 530
213 51
213 1466
213 1488
213 74
51 425
425 489
213 83...

result:

ok AC

Test #10:

score: 0
Accepted
time: 2ms
memory: 4660kb

input:

1482 1518
376140462 628145516
186969585 883515280
326402539 762888635
9580638 127860889
646139319 570870044
484027666 178509022
841082555 61263304
940563715 558212774
403573723 902071050
9467290 727123762
491747709 798571510
614608448 789204466
806956091 555253431
528156706 181457954
167035008 87744...

output:

1 10
10 76
10 1046
76 1075
76 1114
1075 1464
1 522
1 880
1 171
1 242
1 520
171 1306
171 493
493 766
10 82
10 732
10 971
82 970
82 1119
10 252
10 1291
10 193
10 876
193 523
523 1337
82 845
82 547
82 624
82 1083
547 1171
547 1352
547 1318
82 419
82 1338
419 1252
1 888
10 811
1 65
1 255
1 727
65 181
18...

result:

ok AC

Test #11:

score: 0
Accepted
time: 2ms
memory: 4700kb

input:

1490 1510
207579012 1361955
186969585 883515280
326402539 762888635
158176572 98152102
940563715 558212774
496147999 579113528
837151740 925801172
9467290 727123762
631265400 296231662
520690249 899374333
491747709 798571510
456517316 162733264
528156706 181457954
158398859 751354013
743974602 15204...

output:

1490 1342
1490 5
1490 6
6 290
6 772
290 1202
290 783
1490 448
448 554
554 560
6 17
17 89
6 732
1490 496
496 661
496 768
496 815
768 1064
1064 1133
6 1338
6 58
6 462
6 1247
462 547
462 561
547 1253
58 91
91 256
91 997
91 1398
6 1378
58 92
58 1013
6 634
58 389
58 130
58 1438
58 147
58 970
970 1344
147...

result:

ok AC