poj 3335 Rotating Scoreboard

 1 #include <cstdio>

 2 #include <cstring>

 3 #include <algorithm>

 4 #include <cmath>

 5 #define maxn 1000000

 6 using namespace std;

 7 

 8 const double eps=(1e-8);

 9 struct point

10 {

11     double x,y;

12 };

13 double a,b,c;

14 int n,cutt=0,m;

15 point p1[maxn];

16 point p2[maxn];

17 point p3[maxn];

18 

19 void get(point c1,point c2)

20 {

21     a=c2.y-c1.y;

22     b=c1.x-c2.x;

23     c=c1.y*c2.x-c1.x*c2.y;

24 }

25 

26 point insertsect(point c1,point c2)

27 {

28     double u=fabs(a*c1.x+b*c1.y+c);

29     double v=fabs(a*c2.x+b*c2.y+c);

30     point p;

31     p.x=(c1.x*v+c2.x*u)/(u+v);

32     p.y=(c1.y*v+c2.y*u)/(u+v);

33     return p;

34 }

35 

36 void cut()

37 {

38     int cutnum=0;

39     for(int i=1; i<=m; i++)

40     {

41         if(a*p3[i].x+b*p3[i].y+c>=0)

42             p2[++cutnum]=p3[i];

43         else

44         {

45             if(a*p3[i-1].x+b*p3[i-1].y+c>0)

46                 p2[++cutnum]=insertsect(p3[i-1],p3[i]);

47             if(a*p3[i+1].x+b*p3[i+1].y+c>0)

48                 p2[++cutnum]=insertsect(p3[i+1],p3[i]);

49         }

50     }

51     for(int i=1; i<=cutnum; i++)

52         p3[i]=p2[i];

53     p3[cutnum+1]=p2[1]; p3[0]=p2[cutnum];

54     m=cutnum;

55 }

56 

57 

58 int main()

59 {

60     int T;

61     scanf("%d",&T);

62     while(T--)

63     {

64         scanf("%d",&n);

65         for(int i=1; i<=n; i++)

66         {

67             scanf("%lf%lf",&p1[i].x,&p1[i].y);

68         }

69         for(int i=1; i<=n; i++)

70         {

71             p3[i]=p1[i];

72         }

73         p1[n+1]=p1[1];

74         p3[n+1]=p3[1];

75         p3[0]=p3[n];

76         m=n;

77         for(int i=1; i<=n; i++)

78         {

79             get(p1[i],p1[i+1]);

80             cut();

81         }

82         if(m==0) printf("NO
");

83         else printf("YES
");

84     }

85     return 0;

86 }