## 10445 - Make Polygon

Moderator: Board moderators

rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France
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?

Just count it as 180 because In this problem you have to find the minimum and maximum angle of Picasso’s polygon. it does not matter the angle is 180 or not.
Rakeb

marong
New poster
Posts: 6
Joined: Thu May 22, 2003 1:44 pm
Location: china
WA again.
and my programme pass all test you give me.

rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France
6
0 0
1 0
2 0
2 2
1 2
0 2

90.000000 180.000000

check this input and output. i think ur prog. gives
90.000000 90.000000

and one more thing, use pi = acos(-1) or pi=2*acos(0)
Rakeb

marong
New poster
Posts: 6
Joined: Thu May 22, 2003 1:44 pm
Location: china
This is my new programme, and all Tips you give me has been used,
but still WAAAAAAAAAAAAAAAAAAAA             Code: Select all

``````# include <stdio.h>
# include <math.h>
# define MaxN 200
# define PI (2*acos(0))

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))
);
}

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);
}

{
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)
{
Clockwise=(Area()<0);
if (Clockwise==0) Clockwise=-1;
MaxArg=0;
MinArg=360;
for (i=0;i<N;i++)
{
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);
}
}``````

marong
New poster
Posts: 6
Joined: Thu May 22, 2003 1:44 pm
Location: china
Can anyone give me help ?
at least give me a AC programme.

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

its hard to understand ur procedure by watching the code only. it would be better if u say ur procedure. so i am describing how i have solved it:

i calculated every angle of the polygon and find the maximum and minimum of them;
first of all i determined the polygon is given in clockwie or anti clock wise order
then i make a triangle for every
i, j and k where i=0 to n
j=(i+1)%n and k=(j+1)%n

then
a=distance(point,poin[j]);
b=distance(point[j],poin[k]);
c=distance(point,poin[k]);

then i calculated the angle between a and b by the formulea

cost(A)=(a*a+b*b-c*c)/(2*a*b);
Where A is angle between a and b;

now if the points of polygon is given in anti clockwise order and if the area of the triangle formed by points i, j, and k is <0 the outer angle between a and b will be calculated by the above formulea but we need the inner angle. so then the inner angle will be 2*pi-A;

same way when the points of polygon is given in clockwise order and if the area of the triangle formed by points i, j, and k is >0 the outer angle between a and b will be calculated by the above formulea but we need the inner angle. so then the inner angle will be 2*pi-A;

otherwise the inner angle is A;

I did the same thing for every point taking as i and updated the maximum and minimum angle

Hope this will help u. Best of luck Rakeb

medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

### 10445 Why WA?

Why WA? Give me some tests or send me AC program, please!

-------------------------------------------------------------
program p10445;
var
x,y:array[0..1000] of integer;
i,n:integer;
Sarea,angle,min,max:double;

function tri(one,two,three:integer):integer;
begin
tri := (x[two] - x[one])*(y[three] - y[one]) - (x[three] - x[one])*(y[two] - y[one]);
end;

function area:double;
var
i,s:integer;
begin
s := 0;
for i:=1 to n-2 do
s := s + tri(i,i+1,i+2);
area := s / 2;
end;

function CountAngle(i:integer):double;
var
temp,a,b,res,ax,ay,bx,by,scalar:double;
begin
ax := x[i-1] - x[i]; ay := y[i-1] - y[i];
bx := x[i+1] - x[i]; by := y[i+1] - y[i];
scalar := ax*bx + ay*by;
if (scalar = 0.0) then
begin
CountAngle := 90.0;Exit;
end;
a := sqrt(ax*ax+ay*ay);
b := sqrt(bx*bx+by*by);
res := scalar / (a*b);
temp := sqrt(1/(res*res) - 1);
temp := ArcTan(temp);
if res < 0 then temp := PI - temp;
if tri(i-1,i,i+1) * Sarea < 0 then temp := 2*PI - temp;
CountAngle := temp*180.0 / PI;
end;

begin
while True do
begin
if n < 3 then break;
for i:=1 to n do
Sarea := area;
x := x[n]; y := y[n];
x[n+1] := x; y[n+1] := y;
min:=360.0; max := 0.0;
for i:=1 to n do
begin
angle := CountAngle(i);
if min > angle then min := angle;
if max < angle then max := angle;
end;
writeln(min:0:6,' ',max:0:6);
end;
end.

juki
New poster
Posts: 2
Joined: Sat Oct 18, 2003 10:55 am

### 10445, clockwise, counter-clockwise

For solving this problem(10445),
As you know, First!! we have to find that input polygon is clockwise, or counter-clockwise;

13
0 7
7 0
14 8
3 15
2 9
3 11
4 12
6 11
8 9
9 8
7 6
5 5
3 5

Is this polygon clockwise??
I think this polygon is counter-clockwise.

Are you agree?

I have two program.

One gets ACC.
another gets WA.
(in online-judge system)

but, the my ACC program make that above polygon is clockwise.
and the my WA program make that above polygon is counter-clockwise.

Surely, two program's output is differnt.

My WA program output is
11.309932 270.000000

My ACC program output is
90.000000 348.690068

I think '11.309932 270.000000' is correct.

Am I incorrect?

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am
Well, I got 11.309932 341.565051 for your's input, but still WA. Maybe the mistake is in Pi, because I use Pascal, and we Pascalists don't have acos fucntion Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am
Well, I got 11.309932 341.565051 for your's input, but still WA. Maybe the mistake is in Pi, because I use Pascal, and we Pascalists don't have acos fucntion fpmc
New poster
Posts: 23
Joined: Tue Sep 30, 2003 11:44 pm
Hey juki,

I have the same problem here, although I have not get a AC solution yet. It's strange how you can treat that polygon as clock-wise? How do you check for clock-wise or counter-clock-wise? Is there a special mechanism for that?

What I did is I add up all the 'inner' angles and the 'outer' angles, by assuming a specific ordering. Then if the sum of the innger angles is bigger, I switch the two. Is this correct?

Can anyone please kindly post some more test input?

Frank

youhan_sun
New poster
Posts: 1
Joined: Sat Jan 11, 2003 12:31 pm
Contact:

### 10445 WA :( --help!

Const
Maxn=30;
e0=1e-10;
pi=3.14159265358979323846;

Type
Point=Record
x,y:Longint;
End;

Var
p:Array[0..Maxn] Of Point;
n:Longint;
Max,Min:Extended;

Procedure Init;
Var
i:Longint;
Begin
For i:=1 To n Do With p Do Read(x,y);
p:=p[n];
p[n+1]:=p;
End;

Function Line(p1,p2:Point):Longint;
Begin
Line:=Sqr(p1.x-p2.x)+Sqr(p1.y-p2.y);
End;

Function Mul(p1,p2,p3:Point):Longint;
Begin
Mul:=(p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x);
End;

Function GetAngle(p1,p2,p3:Point):Extended;
Var
t:Extended;
s,a,b,c:Longint;
Begin
a:=Line(p1,p2);
b:=Line(p2,p3);
c:=Line(p1,p3);
s:=a+b-c;
If s=0 Then
t:=pi/2
Else
Begin
t:=a;
t:=t*b;
t:=Sqrt(t)*2;
If s>e0 Then
Begin
t:=Sqrt(Sqr(t/s)-1);
t:=Arctan(t);
End
Else
Begin
t:=Sqrt(Sqr(t/s)-1);
t:=pi-Arctan(t);
End
End;
If Mul(p1,p2,p3)>0 Then GetAngle:=t*180/pi
Else GetAngle:=360-t*180/pi
End;

Procedure Work;
Var
i:Longint;
s,t,r:Extended;
Begin
Max:=-1e10;
Min:=1e10;
t:=0.0;
r:=0.0;
For i:=1 To n Do
Begin
s:=GetAngle(p[i-1],p,p[i+1]);
t:=t+s;
r:=r+360-s;
If s>Max+e0 Then Max:=s;
If s<Min-e0 Then Min:=s;
End;
If t<r-e0 Then Writeln(Min:0:6,' ',Max:0:6)
Else Writeln(360-Max:0:6,' ',360-Min:0:6);
End;

Begin
// Assign(Input,'10445.in');
// Reset(Input);
While n>=3 Do
Begin
Init;
Work;
End;
End.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Thanks for the test case above, juki. I've got Accepted at last~

By the way, for your case, my output gives:

Code: Select all

``11.309932 270.000000``
...
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

arif_pasha
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm
Contact:

### 10445 - make polygon wa???

can anyone tell me what is wrong with my code? it gets wa all the time..
thanks . [ also some critical test inputs ]

[cpp]

#include <iostream.h>
#include <stdio.h>
#include <math.h>

class point
{
public:
double x,y;
};

point p;

int order; // clock = -1 anticlk = 1
const double Pi = acos(-1.0);
const double epsilon = 1e-18;

/**
returns 1[ if the points of the polygon is anticlkwise]
returns -1[ if the points of the polygon is clkwise]
*/
int clkwise(int n)
{
double area = 0.0;
int i;

for( i=0; i<n; i++ )
area += p.x*p[(i+1)%n].y - p[(i+1)%n].x*p.y;

return (area)>=0.0?1:-1;
}

double distance(point a,point b)
{
double xx,yy;

xx = a.x - b.x;
yy = a.y - b.y;

return sqrt(xx*xx + yy*yy);
}

/**
retruns the sign of the area formed by a,b,c points
*/
int AreaSign(point a,point b,point c)
{
double s = 0;

s += a.x*(b.y - c.y);
s += b.x*(c.y - a.y);
s += c.x*(a.y - b.y);

return (s)>=0.0?1:-1;
}

double findangle(point u,point v,point w)
{
double ang,val;
double a,b,c;

int areaSign;

a = distance(u,v);
b = distance(v,w);
c = distance(w,u);

val = ( a*a + b*b - c*c )/( 2*a*b );

/* angle between triangles arm a and b */
ang = acos(val);

areaSign = AreaSign(u,v,w);

if(order == -1) // clkwise
{
if(areaSign == -1)
ang = 2*Pi - ang;
}
else // counter clkwise
{
if(areaSign == -1)
ang = 2*Pi - ang;
}

return ang;
}

int main()
{
int i,j,k,n;
double ang;
double min = 1e30,max=0.0;

while(scanf("%d",&n)==1 && n)
{
for(i=0;i<n;i++)
scanf("%lf %lf",&p.x,&p.y);

order = clkwise(n);

for(i=0;i<n;i++)
{
j = (i+1)%n;
k = (j+1)%n;

ang = findangle(p,p[j],p[k]);

if(min>ang)
min = ang;
if(ang<max)
max = ang;
}

min = min * 180.0 / Pi;
max = max * 180.0 / Pi;

printf("%.6lf %.6lf\n",min,max);

min = 1e30;
max = 1e-30;
}
return 0;
}
[/cpp]

Deci
New poster
Posts: 3
Joined: Thu Mar 16, 2006 12:33 pm

### 10445 - Passes al the tests but WA

Hi everybody!
I have been doing this problem for some days but it still resists.
The following code passes all the tests that I have found in the forum. Have anybody an idea which case doesn't work?
Thanks

int main(){
double x,y;
int num_punts=3,i;
bool first=true;
double angle_min,angle_max,num,denom,v11,v12,v21,v22,salida,pi,angle_total;
pi=acos(-1);
angle_min=360;
angle_max=0;

while((num_punts>=3)&&(cin >> num_punts)){
if(num_punts>=3){
angle_total=0;
for(i=0;i<num_punts;i++) cin >> x >> y;
for(i=0;i<num_punts;i++){
v11=x[i%num_punts]-x[(i+1)%num_punts];
v12=y[i%num_punts]-y[(i+1)%num_punts];
v21=x[(i+2)%num_punts]-x[(i+1)%num_punts];
v22=y[(i+2)%num_punts]-y[(i+1)%num_punts];
num=v11*v21+v12*v22;
denom=sqrt((v11*v11+v12*v12)*(v21*v21+v22*v22));
if (v11*v22-v21*v12>0){
salida=acos(num/denom)*180/pi;
}else{
salida=360-acos(num/denom)*180/pi;
}
if(salida>=360) salida=salida-360;
if(salida<0) salida=salida+360;
if(salida>angle_max) angle_max=salida;
if(salida<angle_min) angle_min=salida;
angle_total+=salida;
}

if (angle_total!=(num_punts-2)*180){
angle_total=0;
angle_min=360;
angle_max=0;
for(i=0;i<num_punts;i++){
v11=x[i%num_punts]-x[(i+1)%num_punts];
v12=y[i%num_punts]-y[(i+1)%num_punts];
v21=x[(i+2)%num_punts]-x[(i+1)%num_punts];
v22=y[(i+2)%num_punts]-y[(i+1)%num_punts];
num=v11*v21+v12*v22;
denom=sqrt((v11*v11+v12*v12)*(v21*v21+v22*v22));
if (v11*v22-v21*v12<0){
salida=acos(num/denom)*180/pi;
}else{
salida=360-acos(num/denom)*180/pi;
}
if(salida>=360) salida=salida-360;
if(salida<0) salida=salida+360;
if(salida>angle_max) angle_max=salida;
if(salida<angle_min) angle_min=salida;
angle_total+=salida;
}

}

if(angle_max>=360) angle_max=angle_max-360;
if(angle_max<0) angle_max=angle_max+360;

if(angle_min>=360) angle_min=angle_min-360;
if(angle_min<0) angle_min=angle_min+360;
if (angle_min==-0.00000) angle_min=0.00000;
if (angle_max==-0.00000) angle_max=0.00000;
if (angle_min>angle_max) swap(angle_min,angle_max);
printf("%3.6f %3.6f\n",angle_min,angle_max);

}
}

return (0);
}