10575 - Polylops

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10575 Polylops

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. :oops:
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.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

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.
JongMan @ Yonsei

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

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.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

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. :oops:

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

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
New poster
Posts: 4
Joined: Thu Aug 12, 2004 12:05 pm

10575 AC code gets WA now

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
New poster
Posts: 4
Joined: Thu Aug 12, 2004 12:05 pm

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
New poster
Posts: 4
Joined: Thu Aug 12, 2004 12:05 pm

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

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
New poster
Posts: 4
Joined: Thu Aug 12, 2004 12:05 pm

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 :D .

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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

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!

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

Re: 10575 - Polylops

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).
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Post Reply

Return to “Volume 105 (10500-10599)”