QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#304578 | #7511. Planar Graph | NemanjaSo2005 | WA | 1ms | 4308kb | C++14 | 7.6kb | 2024-01-13 21:25:04 | 2024-01-13 21:25:04 |
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){
if(veza[a][b]==2)
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);
// cout<<gran<<" ";
gran|=gduz(niz[i].a,niz[i].c);
// cout<<gran<<" ";
gran|=gduz(niz[i].b,niz[i].c);
// 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;
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: 0
Wrong Answer
time: 1ms
memory: 4308kb
input:
4 1 3 -2 0 0 2 2 0 0 1 0 3 1 2 2 3 1 3
output:
000
result:
wrong answer 1st lines differ - expected: '111', found: '000'