QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#224254 | #7511. Planar Graph | NemanjaSo2005 | WA | 1ms | 4212kb | C++14 | 5.9kb | 2023-10-23 00:50:40 | 2023-10-23 00:50:40 |
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);
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){
int kol=0;
kol+=(x.a==y.a);
kol+=(x.a==y.b);
kol+=(x.a==y.c);
kol+=(x.b==y.a);
kol+=(x.b==y.b);
kol+=(x.b==y.c);
kol+=(x.c==y.a);
kol+=(x.c==y.b);
kol+=(x.c==y.c);
return kol>=2;
}
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++)
kol[1+znak(orijent(p1,p2,A[i]))];
if(kol[0]==0 or kol[2]==0)
return true;
return false;
}
void dfs(int gde){
if(niz[gde].tacka)
return;
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<<T.a<<" "<<T.b<<" "<<T.c<<endl;
// cout<<P.x<<" "<<P.y<<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;
}
if(!dobar)
continue;
//cout<<"TROUGAO "<<a<<" "<<b<<" "<<c<<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;
gran|=gduz(A[niz[i].a],A[niz[i].b]);
gran|=gduz(A[niz[i].a],A[niz[i].c]);
gran|=gduz(A[niz[i].b],A[niz[i].c]);
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;
}
/*
4 1 3
-2 0
0 2
2 0
0 1
0 3
1 2
2 3
1 3
*/
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 4212kb
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: -100
Wrong Answer
time: 1ms
memory: 4156kb
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:
SEKU SE 13 12 23 -22 16 -3 18 4 SEKU SE 13 12 9 -23 23 -22 -17 -13 SEKU SE 13 12 19 -5 16 -3 18 4 SEKU SE 13 12 15 -15 16 -3 12 -1 SEKU SE 13 12 -17 -13 4 -7 -17 11 SEKU SE 16 -3 4 -7 13 12 5 -15 SEKU SE 16 -3 23 -22 18 4 15 -15 SEKU SE 16 -3 9 -23 23 -22 -17 -13 SEKU SE 16 -3 23 11 18 4 15 -15 SEKU...
result:
wrong answer 1st lines differ - expected: '1111111111111', found: 'SEKU SE 13 12 23 -22 16 -3 18 4'