QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#304583 | #7511. Planar Graph | NemanjaSo2005 | WA | 2ms | 4292kb | C++14 | 7.7kb | 2024-01-13 21:28:02 | 2024-01-13 21:28:03 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int N,M,E,K=0;
int veza[105][105];
struct tacka{
int x,y;
bool operator == (const tacka &a){
return x==a.x and y==a.y;
}
tacka operator - (const tacka &a){
tacka ret;
ret.x=x-a.x;
ret.y=y-a.y;
return ret;
}
tacka operator + (const tacka &a){
tacka ret;
ret.x=x+a.x;
ret.y=y+a.y;
return ret;
}
} A[105],B[105];
struct duz{
tacka p1,p2;
void fromcords(int ax,int ay,int bx,int by){
p1.x=ax;
p1.y=ay;
p2.x=bx;
p2.y=by;
}
}dpp;
vector<duz> D;
int znak(int x){
if(x==0)
return 0;
if(x>0)
return 1;
return -1;
}
int orijent(tacka p1,tacka p2,tacka a){
if(p1.x==p2.x)
return znak(p2.y-p1.y)*znak(p1.x-a.x)*-1;
return (p2.y-a.y)*(p2.x-p1.x)-(p2.x-a.x)*(p2.y-p1.y);
}
bool sekuse(tacka a1,tacka a2, tacka b1,tacka b2){
if(a1==b1 or a1==b2 or a2==b1 or a2==b2)
return false;
if(znak(orijent(a1,a2,b1))==znak(orijent(a1,a2,b2)))
return false;
if(znak(orijent(b1,b2,a1))==znak(orijent(b1,b2,a2)))
return false;
return true;
}
void dodajduz(tacka a,tacka b){
duz d;
d.p1=a;
d.p2=b;
D.push_back(d);
}
bool seceneku(duz x){
for(int i=0;i<D.size();i++)
if(sekuse(x.p1,x.p2,D[i].p1,D[i].p2)){
/* cout<<"SEKU SE "<<x.p1.x<<" "<<x.p1.y<<" ";
cout<<x.p2.x<<" "<<x.p2.y<<" ";
cout<<D[i].p1.x<<" "<<D[i].p1.y<<" ";
cout<<D[i].p2.x<<" "<<D[i].p2.y<<endl;*/
return true;
}
return false;
}
struct troug{
int a,b,c;
vector<int> sused;
bool tacka;
} niz[10005];
bool sused(troug x,troug y){
vector<int> ist;
if(x.a==y.a) ist.push_back(x.a);
if(x.a==y.b) ist.push_back(x.a);
if(x.a==y.c) ist.push_back(x.a);
if(x.b==y.a) ist.push_back(x.b);
if(x.b==y.b) ist.push_back(x.b);
if(x.b==y.c) ist.push_back(x.b);
if(x.c==y.a) ist.push_back(x.c);
if(x.c==y.b) ist.push_back(x.c);
if(x.c==y.c) ist.push_back(x.c);
if(ist.size()<2)
return false;
//cout<<"ISTI "<<ist[0]<<" "<<ist[1]<<endl;
return veza[ist[0]][ist[1]]==1;
}
pair<int,int> edg[305];
vector<int> ima[105][105];
bool gduz(int a,int b, bool upit){
if(veza[a][b]==2 and upit)
return false;
tacka p1=A[a];
tacka p2=A[b];
int kol[3]={0,0,0};
for(int i=1;i<=N;i++){
// cout<<znak(orijent(p1,p2,A[i]))<<endl;
kol[1+znak(orijent(p1,p2,A[i]))]++;
}
//cout<<"KRAJ"<<endl;
if(kol[0]==0 or kol[2]==0)
return true;
return false;
}
void dfs(int gde){
if(niz[gde].tacka)
return;
//cout<<"DFS "<<gde<<endl;
niz[gde].tacka=true;
for(int i=0;i<niz[gde].sused.size();i++)
dfs(niz[gde].sused[i]);
return;
}
bool cmp(tacka a,tacka b){
if(a.x<b.x)
return true;
if(a.x>b.x)
return false;
return a.y<b.y;
}
bool pripada(troug T,tacka P){
tacka niz[3]={A[T.a],A[T.b],A[T.c]};
sort(niz,niz+3,cmp);
int orj=znak(orijent(niz[0],niz[1],P));
// cout<<"PRIPADA LI"<<endl;
// cout<<niz[0].x<<" "<<niz[0].y<<" "<<niz[1].x<<" "<<niz[1].y<<" "<<niz[2].x<<" "<<niz[2].y<<" "<<endl;
// cout<<P.x<<" "<<P.y<<endl;
// cout<<orijent(niz[0],niz[1],P)<<" "<<orijent(niz[1],niz[2],P)<<" "<<orijent(niz[2],niz[0],P)<<endl;
if(orj!=znak(orijent(niz[1],niz[2],P)))
return false;
if(orj!=znak(orijent(niz[2],niz[0],P)))
return false;
// cout<<"DA"<<endl;
return true;
}
int main(){
/*while(true){
int a,b,c,d;
tacka a1,a2,b1,b2;
cin>>a1.x>>a1.y;
cin>>a2.x>>a2.y;
cin>>b1.x>>b1.y;
cin>>b2.x>>b2.y;
cout<<sekuse(a1,a2,b1,b2)<<endl;
}*/
cin>>N>>M>>E;
for(int i=1;i<=N;i++){
cin>>A[i].x>>A[i].y;
}
for(int i=1;i<=M;i++){
cin>>B[i].x>>B[i].y;
}
int a,b;
for(int it=1;it<=E;it++){
cin>>a>>b;
if(a>b)
swap(a,b);
veza[a][b]=2;
veza[b][a]=2;
dodajduz(A[a],A[b]);
edg[it]={a,b};
}
for(int i=1;i<=N;i++)
for(int j=i+1;j<=N;j++){
if(veza[i][j])
continue;
duz d;
d.p1=A[i];
d.p2=A[j];
if(seceneku(d))
continue;
D.push_back(d);
// cout<<"DODAJEM "<<i<<" "<<j<<endl;
veza[i][j]=1;
veza[j][i]=1;
}
for(int a=1;a<=N;a++)
for(int b=a+1;b<=N;b++)
for(int c=b+1;c<=N;c++){
if(!veza[a][b])
continue;
if(!veza[a][c])
continue;
if(!veza[b][c])
continue;
bool dobar=true;
for(int it=1;it<=N;it++){
if(it==a or it==b or it==c)
continue;
troug T;
T.a=a;
T.b=b;
T.c=c;
if(pripada(T,A[it])){
dobar=false;
// cout<<"PRIPADA "<<A[it].x<<" "<<A[it].y<<endl;
break;
}
}
if(!dobar)
continue;
// cout<<"DOBAR"<<endl;
K++;
// cout<<"TROUGAO "<<K<<": "<<a<<" "<<b<<" "<<c<<endl;
niz[K].a=a;
niz[K].b=b;
niz[K].c=c;
ima[a][b].push_back(K);
ima[b][a].push_back(K);
ima[a][c].push_back(K);
ima[c][a].push_back(K);
ima[b][c].push_back(K);
ima[c][b].push_back(K);
}
for(int i=1;i<=E;i++){
int a=edg[i].first;
int b=edg[i].second;
/* cout<<a<<" "<<b<<endl;
for(int j=0;j<ima[a][b].size();j++)
cout<<ima[a][b][j]<<" ";
cout<<endl<<endl;*/
}
//cout<<K<<endl;
for(int i=1;i<=K;i++)
for(int j=i+1;j<=K;j++)
if(sused(niz[i],niz[j])){
niz[i].sused.push_back(j);
niz[j].sused.push_back(i);
//cout<<"SUSEDI "<<i<<" "<<j<<endl;
}
for(int i=1;i<=K;i++){
bool gran=false;
// cout<<i<<endl;
gran|=gduz(niz[i].a,niz[i].b,true);
// cout<<gran<<" ";
gran|=gduz(niz[i].a,niz[i].c,true);
// cout<<gran<<" ";
gran|=gduz(niz[i].b,niz[i].c,true);
// cout<<gran<<endl;
if(gran){
niz[i].sused.push_back(K+1);
niz[K+1].sused.push_back(i);
// cout<<"SUSEDI "<<i<<" "<<K+1<<endl;
}
}
/* cout<<"SUSEDI: "<<endl;
for(int i=1;i<=N;i++){
cout<<i<<": ";
for(int p:niz[i].sused)
cout<<p<<" ";
cout<<endl;
}
*/
for(int i=1;i<=K;i++)
for(int j=1;j<=M;j++)
if(pripada(niz[i],B[j])){
dfs(i);
// cout<<"IMA "<<i<<endl;
}
bool post=false;
for(int i=1;i<=M;i++){
// cout<<i<<endl;
bool dob=true;
for(int j=1;j<=K;j++){
// cout<<j<<" "<<pripada(niz[j],B[i])<<endl;
if(pripada(niz[j],B[i]))
dob=false;
}
post|=dob;
}
if(post)
dfs(K+1);
for(int i=1;i<=E;i++){
int a=edg[i].first;
int b=edg[i].second;
int ans=0;
for(int j=0;j<ima[a][b].size();j++)
if(niz[ima[a][b][j]].tacka)
ans=1;
if(gduz(a,b,false) and niz[K+1].tacka)
ans=1;
cout<<ans;
}
cout<<endl;
return 0;
}
/*
10 1 14
-1 8
0 4
4 6
7 3
5 0
2 0
5 3
-3 -2
9 -1
9 8
3 2
1 2
1 8
2 3
2 7
3 4
3 7
4 5
5 6
5 7
8 9
9 10
3 10
10 1
2 8
*/
/*
12 2 13
0 6
2 5
1 2
2 0
3 1
6 1
6 3
7 6
7 9
4 9
5 5
3 4
5 7
2 3
1 2
2 3
2 12
3 4
3 5
5 7
5 12
6 7
7 8
8 9
8 10
10 11
11 12
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4164kb
input:
4 1 3 -2 0 0 2 2 0 0 1 0 3 1 2 2 3 1 3
output:
111
result:
ok single line: '111'
Test #2:
score: 0
Accepted
time: 1ms
memory: 4220kb
input:
13 35 13 13 12 16 -3 18 4 4 -7 23 -22 9 -23 23 11 12 -1 19 -5 15 -15 5 -15 -17 11 -17 -13 -20 19 11 -12 -10 14 -3 14 7 -4 -10 -23 -19 -12 -13 1 -22 10 -21 -1 18 -9 -8 1 13 22 12 -23 -9 -9 -12 -20 4 -3 -6 17 14 -10 10 13 -5 -2 -4 -12 13 22 -18 -21 19 5 12 -18 4 0 3 -17 5 -2 -2 0 8 0 -8 1 14 -18 3 -9 ...
output:
1111111111111
result:
ok single line: '1111111111111'
Test #3:
score: 0
Accepted
time: 2ms
memory: 4292kb
input:
68 59 168 51 -57 -26 -51 -31 58 -45 -78 -46 -49 -53 14 76 -69 -64 32 58 -49 -1 12 -65 28 -15 -10 29 -53 25 -32 78 -41 24 -37 69 56 54 -10 3 36 -18 46 53 -30 41 -2 -30 13 -58 -37 -20 42 -48 -38 -42 22 64 0 9 -56 7 -11 -66 -23 19 -9 -26 -6 -61 -68 57 13 -13 50 -15 -11 -77 47 -77 57 78 51 -37 56 -75 24...
output:
011111111111111111100001011000001001110111110111101011011001111110011011101111110111011101001000000001010100111111100110000100110100101101111111110011001111111100100011
result:
ok single line: '011111111111111111100001011000...1111111110011001111111100100011'
Test #4:
score: 0
Accepted
time: 1ms
memory: 4212kb
input:
59 1 158 -51 8 50 48 -56 -67 19 7 33 -47 32 44 42 47 -36 -57 15 34 -8 23 -24 43 20 11 61 -41 58 -11 -68 -45 36 -54 -21 42 -28 -49 -28 -31 -34 20 29 -65 -13 38 -22 -36 -30 11 -40 57 64 -69 65 51 47 34 -41 31 -1 35 28 -11 58 58 13 12 -52 43 40 6 46 48 46 -59 -52 30 69 -23 -34 38 -1 -5 -12 -27 -11 24 -...
output:
00000000000000000000000000000000000000000000000000000000000001000000000000000000000000000001000000000000000000000000000000000000000000000000001000000000000000
result:
ok single line: '000000000000000000000000000000...0000000000000001000000000000000'
Test #5:
score: 0
Accepted
time: 2ms
memory: 4288kb
input:
92 1 125 55 10 67 -85 -26 80 36 -32 44 -64 41 -50 -93 -80 -66 -92 -68 27 -79 9 87 -61 -40 -64 89 100 75 -42 59 40 60 -30 -66 27 63 90 -19 100 24 -20 -13 83 -100 -92 -83 58 -33 -70 74 -20 -55 73 -41 28 27 -31 -37 -22 40 18 -3 -2 70 79 71 29 32 -73 39 -1 17 -95 -61 56 94 -10 -79 -66 -84 87 -16 71 52 4...
output:
10010010000101001010010100101100100000001010001000000001101111101000011111000000001011000100000010100000000100011011000000110
result:
ok single line: '100100100001010010100101001011...0010100000000100011011000000110'
Test #6:
score: 0
Accepted
time: 0ms
memory: 4216kb
input:
85 47 204 48 93 -32 10 71 70 -37 10 20 -12 -32 -56 1 -22 -46 -64 56 82 -19 63 -5 83 16 89 79 81 51 -22 43 59 33 -87 28 67 -18 38 -16 -23 18 -78 87 66 -83 29 36 58 6 -2 68 80 18 -34 -17 59 -31 -12 -37 -75 33 -79 -51 -24 -88 6 -19 62 71 -78 -51 72 -49 -45 21 41 -58 33 46 67 -11 -31 62 46 54 55 37 -14 ...
output:
000110010001001101100010110101100100011110011110110101010100110011111010101110101001001011100000110101000100010011100100100110100001011010001010001010000100011000001101010110011001101111010000011001000011
result:
ok single line: '000110010001001101100010110101...0011001101111010000011001000011'
Test #7:
score: -100
Wrong Answer
time: 1ms
memory: 4236kb
input:
59 96 152 -75886847 147807525 335545968 317138952 262969730 -308175740 91308409 -162085508 -397786268 -191693417 -227565597 195627938 45666011 253210394 -311142459 58197832 -412164189 -270215767 -12639523 -314154358 -269901472 -366179516 -306681757 -167771007 194329800 -339296479 -12501616 -15788817...
output:
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
result:
wrong answer 1st lines differ - expected: '011101111111111111101011101110...1110001111100010111110111111111', found: '000000000000000000000000000000...0000000000000000000000000000000'