QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#304583#7511. Planar GraphNemanjaSo2005WA 2ms4292kbC++147.7kb2024-01-13 21:28:022024-01-13 21:28:03

Judging History

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

  • [2024-01-13 21:28:03]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:4292kb
  • [2024-01-13 21:28:02]
  • 提交

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
*/

詳細信息

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'