HDU3952-几何

题意：给n个水果，每个水果包括m个点（即m条边），判断一刀能切的最多的水果数目；

思路：数据比较小，n <= 10,m <= 10;可以暴力枚举，枚举两个水果的任意两个点，连成一条直线，然后枚举其他的水果上的两个点，看该直线是否能切过水果（即判断两条线段是否相交）；

当时我们想到了这个方法，但是觉得遇到下图的情况怎么办？于是就否定了这个想法，多往下想一步就好了，不过很多时候都是差这一步，想改过来的话得多锻炼；

这种情况不会发生，因为如果1在2,3中间的话，那么枚举1和2的时候，一定能切到3。

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<stack>

 #include<queue>

 #include<string>

 #include<map>

 #include<set>

 #define maxn 11

 #define INF

 #define eps 1e-8

 #define zero(x) (((x)>0?(x):-(x))<eps)

 #define _sign(x) ((x)>eps?1:((x)<-eps?2:0))

 using namespace std;

 #define rep(i,n) for(int i=0;i<n;i++)

 #define rep1(i,x,y) for(int i=x;i<=y;i++)

 int T,m;

 int n[maxn];

 struct point

 {

     double x,y;

 } p[maxn][];

 double xmult(point p1,point p2,point p0)

 {

     return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);

 }

 int opposite(point p1,point p2,point l1,point l2)

 {

     return xmult(l1,p1,l2)*xmult(l1,p2,l2)<-eps||fabs(xmult(l1,p1,l2)*xmult(l1,p2,l2))<eps;

 }

 int main()

 {

     scanf("%d",&T);

     for(int cas=; cas<=T; cas++)

     {

         scanf("%d",&m);

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

         {

             scanf("%d",&n[i]);

             for(int j=; j<n[i]; j++)

             {

                 scanf("%lf %lf",&p[i][j].x,&p[i][j].y);

             }

         }

         int cnt=;

         int maxx=-;

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

             for(int j=; j<n[i]; j++)

                 for(int k=; k<m; k++)

                     for(int q=; q<n[k]; q++)

                     {

                         cnt=;

                         for(int w=; w<m; w++)

                         {

                             int flag=;

                             for(int u=; u<n[w]; u++)

                             {

                                 for(int v=; v<n[w]; v++)

                                 {

                                     if(opposite(p[w][u],p[w][v],p[i][j],p[k][q]))

                                     {

                                         cnt++;

                                         flag=;

                                         break;

                                     }

                                 }

                                 if(flag)

                                     break;

                             }

                         }

                         maxx=max(maxx,cnt);

                     }

         printf("Case %d: %d\n",cas,maxx);

     }

     return ;

 }