QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#224343 | #7511. Planar Graph | NemanjaSo2005 | WA | 2ms | 4608kb | C++14 | 6.8kb | 2023-10-23 01:27:18 | 2023-10-23 01:27:18 |
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(tacka p1,tacka p2){
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;
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<<"TROUGAO "<<a<<" "<<b<<" "<<c<<endl;
//cout<<"DOBAR"<<endl;
K++;
niz[K].a=a;
niz[K].b=b;
niz[K].c=c;
ima[a][b].push_back(K);
ima[a][c].push_back(K);
ima[b][c].push_back(K);
ima[b][a].push_back(K);
ima[c][a].push_back(K);
ima[c][b].push_back(K);
}
//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(A[niz[i].a],A[niz[i].b]);
// cout<<gran<<" ";
gran|=gduz(A[niz[i].a],A[niz[i].c]);
// cout<<gran<<" ";
gran|=gduz(A[niz[i].b],A[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;
}
}
for(int i=1;i<=K;i++)
for(int j=1;j<=M;j++)
if(pripada(niz[i],B[j]))
dfs(i);
bool post=false;
for(int i=1;i<=M;i++){
bool dob=true;
for(int j=1;j<=K;j++)
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;
}
/*
12 1 12
0 0
1 0
2 1
1 2
0 2
-1 1
2 -1
3 1
2 3
-1 3
-2 1
-1 -1
1 1
1 2
2 3
3 4
4 5
5 6
6 1
7 8
8 9
9 10
10 11
11 12
12 7
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4608kb
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: 0ms
memory: 4376kb
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: -100
Wrong Answer
time: 2ms
memory: 4424kb
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:
011111111111111111100001011000001001110111110111101011011001111110011011101111110111011101011000000101010100111111100111000100111100111101111111110011001111111100100011
result:
wrong answer 1st lines differ - expected: '011111111111111111100001011000...1111111110011001111111100100011', found: '011111111111111111100001011000...1111111110011001111111100100011'