OJ Board

Code: Select all

#include <iostream.h>
#include <math.h>
#include <iomanip.h>
long p(long x1,long y1,long x2,long y2)
	{
	if (x1*y2-x2*y1>0) return 1;
	return 0;
	}
double l(long x1,long y1)
	{
	return sqrt(double(x1*x1)+double(y1*y1));
	}
double angle(long x1,long y1,long x2,long y2)
	{
	double a=double(x1*x2+y1*y2)/double(l(x1,y1)*l(x2,y2));
	a=acos(a);
	return (90.0*a)/acos(0.0);
	}
int main()
	{
	long n,i;
	long x[20],y[20];
	cin>>n;
	while (n>=3)
		{
		double mina=-1,maxa=-1;
		for (i=0;i<n;i++)
			cin>>x[i]>>y[i];
		int min=0;
		for (i=0;i<n;i++)
			if (x[min]>x[i]) min=i;
		long k;
		if (y[(min+1)%n]>y[(min+n-1)%n]) k=-1;
		else k=1;
		for (i=0;i<n;i++)
			{
			long x1=x[min%n],y1=y[min%n];
			long x2=x[(min+k+n)%n],y2=y[(min+k+n)%n];
			long x3=x[(min+2*k+n)%n],y3=y[(min+2*k+n)%n];
			if (p(x2-x1,y2-y1,x3-x2,y3-y2)==1)
				{
				double teca=angle(x1-x2,y1-y2,x3-x2,y3-y2);
				if (mina==-1 || teca<mina) mina=teca;
				if (maxa==-1 || teca>maxa) maxa=teca;
				}
			else
				{
				double teca=360.0-angle(x1-x2,y1-y2,x3-x2,y3-y2);
				if (mina==-1 || teca<mina) mina=teca;
				if (maxa==-1 || teca>maxa) maxa=teca;
				}
			min+=k;
			if (min<0) min+=n;
			}
		cout.setf(ios::fixed);
		cout.setf(ios::showpoint);

		cout<<setprecision(6)<<mina<<" "<<maxa<<"\n";
		cin>>n;
		}
	return 0;
	}

Code: Select all

4
0 0
5 5
0 10
0 9
4
0 10
0 9
0 0
5 5
0

Code: Select all

# include <stdio.h>
# include <math.h>
# define MaxN 200
# define PI 3.14159265359

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

int Inline(point a,point b,point c)
{
 line t1,t2;

 t1.x=a.x-b.x;
 t1.y=a.y-b.y;
 t2.x=b.x-c.x;
 t2.y=b.y-c.y;
 return(Cross_Product(t1,t2)==0);
}

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++)
	if (!Inline(Polygon[i],Polygon[(i+1)%N],Polygon[(i+N-1)%N]))
	{
          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);
    }
}