10445 - Make Polygon

rakeb · Post by **rakeb** » Fri Jun 13, 2003 6:10 am

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.

marong · Post by **marong** » Fri Jun 13, 2003 7:50 am

WA again.
and my programme pass all test you give me.

rakeb · Post by **rakeb** » Fri Jun 13, 2003 8:59 am

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)

marong · Post by **marong** » Fri Jun 13, 2003 10:15 am

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

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++)
	{
          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 · Post by **marong** » Sun Jun 15, 2003 3:40 pm

Can anyone give me help ?
at least give me a AC programme.

rakeb · Post by **rakeb** » Sun Jun 15, 2003 5:54 pm

sorry for late reply

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

medv · Post by **medv** » Sat Jun 21, 2003 6:47 pm

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
read(n);
if n < 3 then break;
for i:=1 to n do
read(x[i],y[i]);
Sarea := area;
x[0] := x[n]; y[0] := y[n];
x[n+1] := x[1]; y[n+1] := y[1];
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 · Post by **juki** » Sat Oct 18, 2003 11:47 am

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

please consider this test case.

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??
Please draw it in your paper with your pen.
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?

(sorry, my bad english)

Dmytro Chernysh · Post by **Dmytro Chernysh** » Thu Oct 30, 2003 1:49 pm

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 · Post by **Dmytro Chernysh** » Thu Oct 30, 2003 1:50 pm

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 · Post by **fpmc** » Wed Dec 10, 2003 3:18 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 · Post by **youhan_sun** » Thu Jul 15, 2004 10:55 am

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[0]:=p[n];
p[n+1]:=p[1];
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);
Read(n);
While n>=3 Do
Begin
Init;
Work;
Read(n);
End;
End.

Observer · Post by **Observer** » Sat Jul 24, 2004 5:11 am

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

...

arif_pasha · Post by **arif_pasha** » Thu Sep 16, 2004 8:09 pm

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[250];

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 · Post by **Deci** » Thu Mar 16, 2006 12:44 pm

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[21],y[21];
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);
}

OJ Board

10445 - Make Polygon

10445 Why WA?

10445, clockwise, counter-clockwise

10445 WA :( --help!

10445 - make polygon wa???

10445 - Passes al the tests but WA