10445  Make Polygon
Moderator: Board moderators
 Ghost77 dimen
 Learning poster
 Posts: 67
 Joined: Sun Sep 22, 2002 5:40 am
 Location: Taiwan
10445  Make Polygon
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.
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.

 New poster
 Posts: 23
 Joined: Mon Dec 16, 2002 8:01 pm
 Location: Portugal
 Contact:
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/
http://www.fe.up.pt/~ei01081/scripts/

 Experienced poster
 Posts: 193
 Joined: Thu Sep 19, 2002 6:39 am
 Location: Indonesia
 Contact:
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 counterclockwise 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 points can be in clockwise or counterclockwise 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).

 New poster
 Posts: 24
 Joined: Mon Feb 24, 2003 5:08 pm
10445
I can't find a mistake!
Help, please.
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*y2x2*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+n1)%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(x2x1,y2y1,x3x2,y3y2)==1)
{
double teca=angle(x1x2,y1y2,x3x2,y3y2);
if (mina==1  teca<mina) mina=teca;
if (maxa==1  teca>maxa) maxa=teca;
}
else
{
double teca=360.0angle(x1x2,y1y2,x3x2,y3y2);
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;
}

 Experienced poster
 Posts: 193
 Joined: Thu Sep 19, 2002 6:39 am
 Location: Indonesia
 Contact:
Could you try this input (both polygons are the same):
I hope it conforms to the inputdescription.
turuthok
Code: Select all
4
0 0
5 5
0 10
0 9
4
0 10
0 9
0 0
5 5
0
turuthok
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
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
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)
Born from ashes  restarting counter of problems (800+ solved problems)
10445 WA
I don't know why I got WA
can Anyone give me the input/output file?
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.yb.x*a.y);
}
double arg(line a,line b)
{
if (Cross_Product(a,b)*Clockwise<0)
return(
PIacos((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.xb.x;
t1.y=a.yb.y;
t2.x=b.xc.x;
t2.y=b.yc.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+N1)%N]))
{
t1.x=Polygon[i].xPolygon[(i+N1)%N].x;
t1.y=Polygon[i].yPolygon[(i+N1)%N].y;
t2.x=Polygon[(i+1)%N].xPolygon[i].x;
t2.y=Polygon[(i+1)%N].yPolygon[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);
}
}