10445 - Make Polygon

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

Moderator: Board moderators

User avatar
Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

10445 - Make Polygon

Post by Ghost77 dimen » Tue Feb 11, 2003 6:23 pm

I use formula to get the max and min angle.

But it doesn't work.

How to calculate for higher precision, thanks?

My formula are

1. cosine law

2. vector law

Or the test data has tricks is the main reason of wrong answer.

Please let me know, thanks. 8)

RuiFerreira
New poster
Posts: 23
Joined: Mon Dec 16, 2002 8:01 pm
Location: Portugal
Contact:

Post by RuiFerreira » Tue Feb 11, 2003 9:44 pm

I'm having the same problem :(
Please visit my webpage!! I've got a lot of UVA statistics scripts
http://www.fe.up.pt/~ei01081/scripts/

User avatar
cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:

Post by cytse » Wed Feb 12, 2003 7:33 am

i think the polygon maybe concave

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Wed Feb 12, 2003 8:55 am

I almost gave up during the contest for this ... but I noticed that there are some important points that led to my AC here:

-> The points can be in clockwise or counter-clockwise order.
-> There might be > 180 angles.
-> I don't care whether or not we have 3 consecutive points being colinear, I treated the angle as 180 degree angle instead of ignoring it.
-> The polygon is not necessarily convex.

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

benetin
New poster
Posts: 2
Joined: Thu Feb 13, 2003 11:36 pm

Post by benetin » Thu Feb 13, 2003 11:41 pm

My program handles all of these, but still...

I found sometimes the error appears exactly on the 7th digit. I got 179.999999 instead of 180.000000.

Got WA even if I artifically fix the 180 degree situation. So I wonder the other answers may also wrong due to the precision.?

Can anybody help me?

Pupirev Sergei
New poster
Posts: 24
Joined: Mon Feb 24, 2003 5:08 pm

10445

Post by Pupirev Sergei » Mon Feb 24, 2003 5:14 pm

I can't find a mistake!
Help, please.

Code: Select all

#include <iostream.h>
#include <math.h>
#include <iomanip.h>
long p(long x1,long y1,long x2,long y2)
	{
	if (x1*y2-x2*y1>0) return 1;
	return 0;
	}
double l(long x1,long y1)
	{
	return sqrt(double(x1*x1)+double(y1*y1));
	}
double angle(long x1,long y1,long x2,long y2)
	{
	double a=double(x1*x2+y1*y2)/double(l(x1,y1)*l(x2,y2));
	a=acos(a);
	return (90.0*a)/acos(0.0);
	}
int main()
	{
	long n,i;
	long x[20],y[20];
	cin>>n;
	while (n>=3)
		{
		double mina=-1,maxa=-1;
		for (i=0;i<n;i++)
			cin>>x[i]>>y[i];
		int min=0;
		for (i=0;i<n;i++)
			if (x[min]>x[i]) min=i;
		long k;
		if (y[(min+1)%n]>y[(min+n-1)%n]) k=-1;
		else k=1;
		for (i=0;i<n;i++)
			{
			long x1=x[min%n],y1=y[min%n];
			long x2=x[(min+k+n)%n],y2=y[(min+k+n)%n];
			long x3=x[(min+2*k+n)%n],y3=y[(min+2*k+n)%n];
			if (p(x2-x1,y2-y1,x3-x2,y3-y2)==1)
				{
				double teca=angle(x1-x2,y1-y2,x3-x2,y3-y2);
				if (mina==-1 || teca<mina) mina=teca;
				if (maxa==-1 || teca>maxa) maxa=teca;
				}
			else
				{
				double teca=360.0-angle(x1-x2,y1-y2,x3-x2,y3-y2);
				if (mina==-1 || teca<mina) mina=teca;
				if (maxa==-1 || teca>maxa) maxa=teca;
				}
			min+=k;
			if (min<0) min+=n;
			}
		cout.setf(ios::fixed);
		cout.setf(ios::showpoint);

		cout<<setprecision(6)<<mina<<" "<<maxa<<"\n";
		cin>>n;
		}
	return 0;
	}

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Tue Feb 25, 2003 2:52 am

Could you try this input (both polygons are the same):

Code: Select all

4
0 0
5 5
0 10
0 9
4
0 10
0 9
0 0
5 5
0
I hope it conforms to the input-description.

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

Pupirev Sergei
New poster
Posts: 24
Joined: Mon Feb 24, 2003 5:08 pm

Post by Pupirev Sergei » Tue Feb 25, 2003 6:01 am

Thanks!
I got AC!

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Apr 10, 2003 8:43 am

It's possible, that input looks like:
4 0 0 1 0 1 1000 1 0
??
My program fails only on such case I think ....

DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

marong
New poster
Posts: 6
Joined: Thu May 22, 2003 1:44 pm
Location: china

10445 WA

Post by marong » Tue Jun 10, 2003 12:55 pm

I don't know why I got WA
can Anyone give me the input/output file?

Code: Select all

# include <stdio.h>
# include <math.h>
# define MaxN 200
# define PI 3.14159265359

struct Tpoint
{ long x; long y;}
Polygon[MaxN];

typedef struct Tpoint line;
typedef struct Tpoint point;

int N;
int Clockwise;

double LineDis(line a)
{
 return(sqrt(a.x*a.x+a.y*a.y));
}

long Cross_Product(line a,line b)
{
 return(a.x*b.y-b.x*a.y);
}

double arg(line a,line b)
{
 if (Cross_Product(a,b)*Clockwise<0)
    return(
	   PI-acos((a.x*b.x+a.y*b.y)/LineDis(a)/LineDis(b))
          );
 else
    return(
	   PI+acos((a.x*b.x+a.y*b.y)/LineDis(a)/LineDis(b))
          );
}

int Inline(point a,point b,point c)
{
 line t1,t2;

 t1.x=a.x-b.x;
 t1.y=a.y-b.y;
 t2.x=b.x-c.x;
 t2.y=b.y-c.y;
 return(Cross_Product(t1,t2)==0);
}

long Area(void)
{
  int i;
  long s=0;

  for (i=0;i<N;i++)
    s+=Cross_Product(Polygon[i],Polygon[(i+1)%N]);
  return(s/2);
}

void ReadInput(void)
{
 int i;
 for (i=0;i<N;i++)
    scanf("%ld %ld",&Polygon[i].x,&Polygon[i].y);
}

main()
{
 int i;
 double MaxArg,MinArg;
 double CurArg;
 line t1,t2;

  while (scanf("%d",&N),N>=3)
    {
      ReadInput();
      Clockwise=(Area()<0);
      if (Clockwise==0) Clockwise=-1;
      MaxArg=0;
      MinArg=360;
      for (i=0;i<N;i++)
	if (!Inline(Polygon[i],Polygon[(i+1)%N],Polygon[(i+N-1)%N]))
	{
          t1.x=Polygon[i].x-Polygon[(i+N-1)%N].x;
	  t1.y=Polygon[i].y-Polygon[(i+N-1)%N].y;
	  t2.x=Polygon[(i+1)%N].x-Polygon[i].x;
	  t2.y=Polygon[(i+1)%N].y-Polygon[i].y;
	  CurArg=arg(t1,t2)/PI*180;
          if (MaxArg<CurArg)
             MaxArg=CurArg;
	  if (MinArg>CurArg)
             MinArg=CurArg;
        }
      printf("%0.6f %0.6f\n",MinArg,MaxArg);
    }
}

User avatar
rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France

Post by rakeb » Tue Jun 10, 2003 6:51 pm

5
-1 0
1 0
1 10
0 5
-1 5

the output is:

11.309932 258.690068

i think it will help u :D. try to assign pi=acos(-1) or 2*acos(0). in this problem points may be given in clockwise or anticlockwise order. so u have to handle this case.
Rakeb

lowai
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm

Post by lowai » Wed Jun 11, 2003 3:09 am

will the polygon be concave?

marong
New poster
Posts: 6
Joined: Thu May 22, 2003 1:44 pm
Location: china

Post by marong » Wed Jun 11, 2003 6:02 am

:cry: Sorry,but I got the exactly correct answer about the case,

Have you any other case?

User avatar
rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France

Post by rakeb » Wed Jun 11, 2003 5:06 pm

6
0 0
1 0
1 10
0 5
-1 10
-1 0

20
0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
9 1
8 1
7 1
6 1
5 1
4 1
3 1
2 1
1 1
0 1

outputs are:

11.309932 337.380135
90.000000 180.000000

to lowai:
will the polygon be concave?
u read the problem statement carefully. then u will find it.
Rakeb

marong
New poster
Posts: 6
Joined: Thu May 22, 2003 1:44 pm
Location: china

Post by marong » Thu Jun 12, 2003 10:23 am

:( :(
I puzzled.
if there are three point p p[i+1] p[i+2] in one line,
Should I ignore it or just count it as 180?

I has submitted two programme of these,
neither is ac.

Post Reply

Return to “Volume 104 (10400-10499)”