QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#304409#7511. Planar GraphNemanjaSo2005WA 2ms4572kbC++146.9kb2024-01-13 19:23:502024-01-13 19:23:51

Judging History

你现在查看的是最新测评结果

  • [2024-01-13 19:23:51]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:4572kb
  • [2024-01-13 19:23:50]
  • 提交

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;
      A[i].x+=1e9+1;
      A[i].y+=1e9+1;
   }
   for(int i=1;i<=M;i++){
      cin>>B[i].x>>B[i].y;
      B[i].x+=1e9+1;
      B[i].y+=1e9+1;
   }
   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 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: 4492kb

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: 4316kb

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: 4572kb

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'