RT,孩子调了 2h 没整出来
最后盯着代码看了 1h 也没发现什么错误。求问,这题是有什么隐蔽的细节吗?
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,ok=1,cnt1,cnt2,e1,e2,bj1[21],bj2[21];
struct seg
{
int l,r,x;
} s1[1000001],s2[1000001],n1[1000001],n2[1000001];
bool cmpp(seg a1,seg a2){return a1.x<a2.x;}
bool cmp(seg a1,seg a2){return a1.l<a2.l;}
bool check(int op1,seg s1,int op2,seg s2)
{
// s1 是纵向线段,s2 是横向线段
if(s1.x<s2.l||s1.x>s2.r) return 0;
if(s2.x<s1.l||s2.x>s1.r) return 0;
return 1;
}
void findt()
{
if(!ok) return;
for(int i=1;i<=7;i++)
for(int j=1;j<=8;j++)
if(n2[j].r==n1[i].x&&n1[i].l<n2[j].x&&n1[i].r>n2[j].x)
{
int flag=1;
for(int ii=1;ii<=7;ii++)
if(ii!=i)
if(check(2,n2[j],1,n1[ii])){flag=0;break;}
for(int ii=1;ii<=8;ii++)
if(ii!=j)
if(check(2,n2[ii],1,n1[i])){flag=0;break;}
if(flag){bj1[i]=1;bj2[j]=1;return;}
}
ok=0;
// printf("#1\n");
}
void findh()
{
if(!ok) return;
for(int i=1;i<=7;i++)
for(int j1=1;j1<=8;j1++)
for(int j2=1;j2<=8;j2++)
{
if(bj1[i]||bj2[j1]||bj2[j2]) continue;
if(j1==j2) continue;
if(n2[j1].l!=n2[j2].l||n2[j1].r!=n2[j2].r||n2[j1].x==n2[j2].x) continue;
if(n1[i].l==min(n2[j1].x,n2[j2].x)&&n1[i].r==max(n2[j1].x,n2[j2].x)&&n2[j1].l<n1[i].x&&n1[i].x<n2[j1].r)
{
int flag=1;
for(int ii=1;ii<=7;ii++)
if(ii!=i)
if(check(2,n2[j1],1,n1[ii])||check(2,n2[j2],1,n1[ii])){flag=0;break;}
for(int ii=1;ii<=8;ii++)
if(ii!=j1&&ii!=j2)
if(check(2,n2[ii],1,n1[i])){flag=0;break;}
if(flag){bj1[i]=1;bj2[j1]=1;bj2[j2]=1;return;}
}
}
ok=0;
// printf("#2\n");
}
void findu()
{
if(!ok) return;
for(int i=1;i<=7;i++)
for(int j1=1;j1<=8;j1++)
for(int j2=1;j2<=8;j2++)
{
if(bj1[i]||bj2[j1]||bj2[j2]) continue;
if(j1==j2) continue;
if(n2[j1].l!=n2[j2].l||n2[j1].r!=n2[j2].r||n2[j1].x==n2[j2].x) continue;
if(n1[i].l==min(n2[j1].x,n2[j2].x)&&n1[i].r==max(n2[j1].x,n2[j2].x)&&n2[j1].l==n1[i].x)
{
int flag=1;
for(int ii=1;ii<=7;ii++)
if(ii!=i)
if(check(2,n2[j1],1,n1[ii])||check(2,n2[j2],1,n1[ii])){flag=0;break;}
for(int ii=1;ii<=8;ii++)
if(ii!=j1&&ii!=j2)
if(check(2,n2[ii],1,n1[i])){flag=0;break;}
if(flag){bj1[i]=1;bj2[j1]=1;bj2[j2]=1;return;}
}
}
ok=0;
// printf("#3\n");
}
void findc()
{
if(!ok) return;
for(int i1=1;i1<=7;i1++)
for(int i2=1;i2<=7;i2++)
for(int j=1;j<=8;j++)
{
if(bj1[i1]||bj1[i2]||bj2[j]) continue;
if(i1==i2) continue;
if(n1[i1].l!=n1[i2].l||n1[i1].r!=n1[i2].r||n1[i1].x==n1[i2].x) continue;
if(n2[j].l==min(n1[i1].x,n1[i2].x)&&n2[j].r==max(n1[i1].x,n1[i2].x)&&n1[i1].l==n2[j].x)
{
int flag=1;
for(int ii=1;ii<=7;ii++)
if(ii!=i1&&ii!=i2)
if(check(2,n2[j],1,n1[ii])){flag=0;break;}
for(int ii=1;ii<=8;ii++)
if(ii!=j)
if(check(2,n2[ii],1,n1[i1])||check(2,n2[ii],1,n1[i2])){flag=0;break;}
if(flag){bj1[i1]=1;bj1[i2]=1;bj2[j]=1;return;}
}
}
ok=0;
// printf("#4\n");
}
void findp()
{
if(!ok) return;
for(int i1=1;i1<=7;i1++)
for(int i2=1;i2<=7;i2++)
for(int j1=1;j1<=8;j1++)
for(int j2=1;j2<=8;j2++)
{
if(bj1[i1]||bj1[i2]||bj2[j1]||bj2[j2]) continue;
if(i1==i2||j1==j2) continue;
if(n1[i1].l!=n1[i2].l||n1[i1].r!=n1[i2].r||n1[i1].x==n1[i2].x) continue;
if(n2[j1].r!=n2[j2].r||n2[j1].l==n2[j2].l||n2[j1].x==n2[j2].x) continue;
if(min(n2[j1].x,n2[j2].x)==n1[i1].l&&max(n2[j1].x,n2[j2].x)==n1[i1].r&&max(n1[i1].x,n1[i2].x)==n2[j1].r)
{
seg S1=n1[i1],S2=n1[i2],S3=n2[j1],S4=n2[j2];
if(S1.x>S2.x) swap(S1,S2);
if(S3.x>S4.x) swap(S3,S4);
if(S3.l<S4.l&&S1.x==S4.l)
{
int flag=1;
for(int ii=1;ii<=7;ii++)
if(ii!=i1&&ii!=i2)
if(check(2,n2[j1],1,n1[ii])||check(2,n2[j2],1,n1[ii])){flag=0;break;}
for(int ii=1;ii<=8;ii++)
if(ii!=j1&&ii!=j2)
if(check(2,n2[ii],1,n1[i1])||check(2,n2[ii],1,n1[i2])){flag=0;break;}
if(flag){bj1[i1]=1;bj1[i2]=1;bj2[j1]=1;bj2[j2]=1;return;}
}
}
}
ok=0;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++)
{
int op,l,r,x;
cin>>op>>l>>r>>x;
if(op==0) s1[++cnt1]={l,r,x};
else s2[++cnt2]={l,r,x};
}
sort(s1+1,s1+1+cnt1,cmpp);sort(s2+1,s2+1+cnt2,cmpp);
for(int l=1,r=1;r<=cnt1;l=r+1)
{
r=l;
while(s1[r+1].x==s1[l].x&&r+1<=cnt1) r++;
sort(s1+l,s1+1+r,cmp);
seg cur=s1[l];
for(int j=l+1;j<=r;j++)
{
if(s1[j].l<=cur.r)
cur.r=s1[j].r;
else
{
n1[++e1]=cur;
cur=s1[j];
}
}
n1[++e1]=cur;
if(r==cnt1) break;
}
for(int l=1,r=1;r<=cnt2;l=r+1)
{
r=l;
while(s2[r+1].x==s2[l].x&&r+1<=cnt2) r++;
sort(s2+l,s2+1+r,cmp);
seg cur=s2[l];
for(int j=l+1;j<=r;j++)
{
if(s2[j].l<=cur.r)
cur.r=s2[j].r;
else
{
n2[++e2]=cur;
cur=s2[j];
}
}
n2[++e2]=cur;
if(r==cnt2) break;
}
if(e1!=7||e2!=8) ok=0;
findc();findp();findu();findh();findt();
cout<<(ok==1?"Yes":"No");
return 0;
}
/*
17
0 1 2 100
0 1 2 -100
0 2 9 90
1 75 90 5
1 65 70 4
1 65 70 6
0 4 6 68
1 50 60 8
1 50 60 20
0 8 20 50
1 52 58 12
1 54 58 16
0 12 16 58
0 12 16 54
1 -100 -99 1
1 -99 -89 1
1 -95 100 1
*/