QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#806893 | #6799. Road Construction | Wuyanru | AC ✓ | 2ms | 4764kb | C++14 | 6.8kb | 2024-12-09 16:34:24 | 2024-12-09 16:34:25 |
Judging History
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