10575 - Polylops

LittleJohn · Post by **LittleJohn** » Sat Feb 28, 2004 9:43 am

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).

Any help would be appreciated and thank you for your reading.

Whinii F. · Post by **Whinii F.** » Sat Feb 28, 2004 2:29 pm

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.

LittleJohn · Post by **LittleJohn** » Sun Feb 29, 2004 5:01 am

Could you explain for me why does 4th polygon have 3 symmetric lines?
I can only find the one, x=1.

Thanks in advance.

Whinii F. · Post by **Whinii F.** » Sun Feb 29, 2004 5:25 am

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.

LittleJohn · Post by **LittleJohn** » Sun Feb 29, 2004 10:54 am

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 · Post by **Divan** » Thu Aug 12, 2004 12:12 pm

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[2000];
int y[2000];
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 · Post by **Divan** » Fri Aug 13, 2004 8:54 am

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.
Please help me, is there a polygon with > 4 (>16) symmetry lines?

Divan · Post by **Divan** » Fri Aug 13, 2004 8:57 am

Forgot to say, my program gives answer 4 for that test, i believe it's correct.

little joey · Post by **little joey** » Fri Aug 13, 2004 10:27 am

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 · Post by **Divan** » Fri Aug 13, 2004 12:44 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.
About test #11.
<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.

What about input

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 · Post by **little joey** » Fri Aug 13, 2004 1:52 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 · Post by **uDebug** » Fri Feb 06, 2015 9:08 am

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).

OJ Board

10575 - Polylops

10575 Polylops

10575 AC code gets WA now

Re: 10575 - Polylops