## 10575 - Polylops

Moderator: Board moderators

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

### 10575 Polylops

I got trouble in solving this problem.
So many people could solve that problem, but not me. My algo is to test all edges and all vertices.
When I fix a candidate symmetric line, I check each vertex one by one that lies on different side of that line.
Here is some test data I made

Code: Select all

``````4
-1000 0 0 1000 1000 0 0 -1000
8
0 0 0 1000 100 1000 100 500 200 500 200 1000 300 1000 300 0
7
-1 0 -1 1 0 1 1 1 1 0 1 -1 -1 -1
5
0 0 0 2 1 1 2 2 2 0
6
0 0 0 2 1 1 2 2 2 0 1 1
5
0 -1 0 2 3 1 4 2 4 -1
7
-1 -1 -1 1 0 2 1 1 1 0 1 -1 0 -2
0
``````
and my output is

Code: Select all

``````Polygon #1 has 4 symmetry line(s).
Polygon #2 has 1 symmetry line(s).
Polygon #3 has 4 symmetry line(s).
Polygon #4 has 1 symmetry line(s).
Polygon #5 has 2 symmetry line(s).
Polygon #6 has 0 symmetry line(s).
Polygon #7 has 2 symmetry line(s).
``````

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
My solution prints
Polygon #1 has 4 symmetry line(s).
Polygon #2 has 1 symmetry line(s).
Polygon #3 has 1 symmetry line(s).
Polygon #4 has 3 symmetry line(s).
Polygon #5 has 2 symmetry line(s).
Polygon #6 has 0 symmetry line(s).
Polygon #7 has 0 symmetry line(s).
It seems your problem is that you ignore points which has parallel incident edges. You cannot ignore them.

In case of polygon 3, there is only one line, which is the y axis.
JongMan @ Yonsei

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
Could you explain for me why does 4th polygon have 3 symmetric lines?
I can only find the one, x=1.

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
Oops.. my program contained an error on the interpretation of the problem. I'm amazed I got accepted along with this bug. Your output seems to be correct on Poly 4.
JongMan @ Yonsei

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
Thank you Whinii, I slightly modified my program but still got WA.
It seems there are some hidden bugs I cannot see.
I'll check it another time.
Thanks again!

Divan
New poster
Posts: 4
Joined: Thu Aug 12, 2004 12:05 pm

### 10575 AC code gets WA now

25.03.2004 I got AC
But now it gets WA
Why?
Self-intersecting polygons in input?

10575 Polylops:

Code: Select all

``````#include <stdio.h>

int x;
int y;
int n;
int npoly;
int symv,syme;
long x0,y0;
bool onvert=false;
bool onedge=false;

void input()
{
scanf("%d",&n);
int i;
for (i=0;i<n;i++)
scanf("%d %d",&x[i],&y[i]);
npoly++;
}

int next(int i)
{
if (i<n-1)
return i+1;
else
return 0;
}

int prev(int i)
{
if (i>0)
return i-1;
else
return n-1;
}

void countvert()
{
int i;
for (i=0;i<n;i++)
{
x0=x[next(i)]+x[prev(i)];
y0=y[next(i)]+y[prev(i)];
if ((x0==x[i]*2)&&(y0==y[i]*2))
onvert=true;
else
{
bool sm=true;
int ii,jj;
ii=next(i);
jj=prev(i);
while (sm&&(ii!=i))
{
if ((x[ii]-x[jj])*(2*x[i]-x0)+(y[ii]-y[jj])*(2*y[i]-y0)!=0)
sm=false;
else
sm=((2*x[ii]-x0)*(2*y[i]-y0)-(2*y[ii]-y0)*(2*x[i]-x0)
-(2*x[i]-x0)*(2*y[jj]-y0)+(2*y[i]-y0)*(2*x[jj]-x0))==0;
ii=next(ii);
jj=prev(jj);
}
if (sm)
symv++;
}
}

}

void countedge()
{
int i;
for (i=0;i<n;i++)
{
long x1,y1;
x0=x[prev(i)]+x[next(next(i))];
y0=y[prev(i)]+y[next(next(i))];
x1=(x[i]+x[next(i)]);
y1=(y[i]+y[next(i)]);
if ((x0==x1)&&(y0==y1))
onedge=true;
else
{
bool sm=true;
int ii,jj;
ii=next(next(i));
jj=prev(i);
while (sm&&(i!=ii))
{
if (((x[ii]-x[jj])*(x1-x0)+(y[ii]-y[jj])*(y1-y0))!=0)
sm=false;
else
sm=((2*x[ii]-x0)*(y1-y0)-(2*y[ii]-y0)*(x1-x0)
-(x1-x0)*(2*y[jj]-y0)+(y1-y0)*(2*x[jj]-x0))==0;
ii=next(ii);
jj=prev(jj);
}
if (sm)
syme++;
}
}
}

void out(int nn)
{
printf("Polygon #%d has %d symmetry line(s)\n",npoly,nn);
}

int main()
{
int i;
npoly=0;
input();
while (n!=0)
{
if ((n&1)==1)
{
syme=0;
symv=0;
for (i=0;i<n;i++)
{
x0=0;
y0=0;
int j;
x0=x[next(i)]+x[prev(i)];
y0=y[next(i)]+y[prev(i)];

if ((x0==x[i]*2)&&(y0==y[i]*2))
{
onvert=true;
}
else
{
bool sm=true;
int ii,jj;
ii=next(i);
jj=prev(i);
while (sm&&(next(jj)!=ii)&&(ii!=jj))
{
if ((x[ii]-x[jj])*(2*x[i]-x0)+(y[ii]-y[jj])*(2*y[i]-y0)!=0)
sm=false;
else
sm=((2*x[ii]-x0)*(2*y[i]-y0)-(2*y[ii]-y0)*(2*x[i]-x0)
-(2*x[i]-x0)*(2*y[jj]-y0)+(2*y[i]-y0)*(2*x[jj]-x0))==0;
ii=next(ii);
jj=prev(jj);
}
if (sm)
symv++;
}
}
out(symv);

}
else
{
onvert=false;
onedge=false;
syme=0;
symv=0;
countvert();
countedge();
out((syme>>1)+(symv>>1));
}

input();
}
return 0;
}
``````

Divan
New poster
Posts: 4
Joined: Thu Aug 12, 2004 12:05 pm
WA is on test #11, polygon has 996 vertices and it is non-degenerate polygon. Correct answer is greater than 16.
Is it possible that answer is > 4.

Divan
New poster
Posts: 4
Joined: Thu Aug 12, 2004 12:05 pm
Forgot to say, my program gives answer 4 for that test, i believe it's correct.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
I'm not sure what you mean. A regular n-gon has n symmetry lines, so the answer could be anything from 0 to 1000 (that is if the vertices of a regular n-gon can be fitted to integer coordinates). I also don't know what you mean by test #11. Am I missing something?
Maybe you could supply some test input for me to run against my AC program. I must confess that I'm too lazy to look into your code...

Divan
New poster
Posts: 4
Joined: Thu Aug 12, 2004 12:05 pm
that is if the vertices of a regular n-gon can be fitted to integer coordinates
By
is there a polygon with > 4 (>16) symmetry lines?
I mean
is there a polygon with > 4 (>16) symmetry lines, which can be fitted to integer coordinates?
I think that only regular 4-gon (square) can.
<submit
>WA
<add "if (n>11) for ( ; ; ) ;" after inputting
>WA
<change to "if (n==11) for ( ; ; ) ;"
>TLE
So it's the test with <=11 polygons, and all previous test have <=11 polygons, and nothing more. I called it test #11 thinking that it's #11 by order of checking.. it is not, but we still can call it so .

Can you submit your AC program once more? If it gets AC then I'll keep on bugsearching.

Code: Select all

``````4
-1 0 0 2 1 0 0 -1
0
4
-1 0 0 2 1 0 0 -1
0
``````
correct output is

Code: Select all

``````Polygon #1 has 1 symmetry line(s).
``````
or

Code: Select all

``````Polygon #1 has 1 symmetry line(s).
Polygon #1 has 1 symmetry line(s).
``````

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
I see. Guess not. I've added the statement assert(lines<=4) to my (still accepted) solution, and it doesn't abort.
The first alternative for your example is, of course, the correct one.
Keep on debugging!

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### Re: 10575 - Polylops

Here is the AC output to LittleJohn's input:

Code: Select all

``````Polygon #1 has 4 symmetry line(s).
Polygon #2 has 1 symmetry line(s).
Polygon #3 has 1 symmetry line(s).
Polygon #4 has 1 symmetry line(s).
Polygon #5 has 2 symmetry line(s).
Polygon #6 has 0 symmetry line(s).
Polygon #7 has 1 symmetry line(s).
``````
Check input and AC output for over 7,500 problems on uDebug!