10445 - Make Polygon

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

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.
Rakeb

marong
New poster
Posts: 6
Joined: Thu May 22, 2003 1:44 pm
Location: china

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

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

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

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)
Rakeb

marong
New poster
Posts: 6
Joined: Thu May 22, 2003 1:44 pm
Location: china

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

marong
New poster
Posts: 6
Joined: Thu May 22, 2003 1:44 pm
Location: china

Post by marong » Sun Jun 15, 2003 3:40 pm

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

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

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 :)
Rakeb

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

10445 Why WA?

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
New poster
Posts: 2
Joined: Sat Oct 18, 2003 10:55 am

10445, clockwise, counter-clockwise

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
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

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
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

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
New poster
Posts: 23
Joined: Tue Sep 30, 2003 11:44 pm

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
New poster
Posts: 1
Joined: Sat Jan 11, 2003 12:31 pm
Contact:

10445 WA :( --help!

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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

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
...
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
Location: Dhaka , Bangladesh
Contact:

10445 - make polygon wa???

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
New poster
Posts: 3
Joined: Thu Mar 16, 2006 12:33 pm

10445 - Passes al the tests but WA

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

Post Reply

Return to “Volume 104 (10400-10499)”