Page 2 of 3

Posted: Fri Jun 13, 2003 6:10 am
by rakeb
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.

Posted: Fri Jun 13, 2003 7:50 am
by marong
WA again.
and my programme pass all test you give me.

Posted: Fri Jun 13, 2003 8:59 am
by rakeb
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)

Posted: Fri Jun 13, 2003 10:15 am
by marong
This is my new programme, and all Tips you give me has been used,
but still WAAAAAAAAAAAAAAAAAAAA :cry: :cry: :cry: :cry:
:cry: :cry: :cry: :cry: :cry: :cry: :cry: :cry: :cry:

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

Posted: Sun Jun 15, 2003 3:40 pm
by marong
Can anyone give me help ?
at least give me a AC programme.

Posted: Sun Jun 15, 2003 5:54 pm
by rakeb
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 :)

10445 Why WA?

Posted: Sat Jun 21, 2003 6:47 pm
by medv
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.

10445, clockwise, counter-clockwise

Posted: Sat Oct 18, 2003 11:47 am
by juki
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)

Posted: Thu Oct 30, 2003 1:49 pm
by Dmytro Chernysh
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 :-(

Posted: Thu Oct 30, 2003 1:50 pm
by Dmytro Chernysh
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 :-(

Posted: Wed Dec 10, 2003 3:18 pm
by fpmc
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

10445 WA :( --help!

Posted: Thu Jul 15, 2004 10:55 am
by youhan_sun
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.

Posted: Sat Jul 24, 2004 5:11 am
by Observer
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
...

10445 - make polygon wa???

Posted: Thu Sep 16, 2004 8:09 pm
by arif_pasha
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]

10445 - Passes al the tests but WA

Posted: Thu Mar 16, 2006 12:44 pm
by Deci
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);
}