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.
# 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);
}
}
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
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.
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
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
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?
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.
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);
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;
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);