这题是让你求一条线能够穿过最多的水果（碰到一个点也算）。
可以证明，，枚举两个点组成的线是可行的。
因为假设有一条线穿过N个水果，那么把它平移一些使得还是穿过N个但是已经不能再平移了，这样的话，这条线肯定是在某个水果的某个端点上。
再以这个端点，旋转这条线，还是穿过N个，直到不能旋转为止（再旋转可能就不能穿过N个了），这样的话，肯定还是这条线碰到了另外一个端点。
所以只要枚举两个端点即可。
只有一个水果的话，特判下。
#include<map>#include<set>#include<queue>#include<stack>#include<math.h>#include<time.h>#include<stdio.h>#include<stdlib.h>#include<iostream>#include<limits.h>#include<string.h>#include<string>#include<algorithm>#define MID(x,y) ( ( x + y ) >> 1 )#define L(x) ( x << 1 )#define R(x) ( x << 1 | 1 )using namespace std;const int MAX = 35;struct point {int x,y;};struct polygon {point p[MAX]; int n; } ;polygon g[MAX];int crossProduct(point a,point b,point c){return (c.x-a.x)*(b.y-a.y) – (b.x-a.x)*(c.y-a.y);}bool s21_inst(point s1,point s2,point l1,point l2){return crossProduct(l1,l2,s1)*crossProduct(l1,l2,s2) <= 0;}int solve(point a,point b,int n){int ans=0;for(int i=0;i<n;i++){int len=g[i].n;g[i].p[len] = g[i].p[0];for(int k=0;k<len;k++)if( s21_inst(g[i].p[k],g[i].p[k+1],a,b) ){ans++;break;}}return ans;}int main(){int ncases,n;int ind=1;scanf("%d",&ncases);while(ncases–){scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&g[i].n);for(int k=0;k<g[i].n;k++)scanf("%d%d",&g[i].p[k].x,&g[i].p[k].y);}if(n==1){printf("Case %d: 1\n",ind++);continue;}int mmax=0;for(int i=0;i<n;i++)for(int k=0;k<g[i].n;k++)for(int j=i+1;j<n;j++)for(int l=0;l<g[j].n;l++){int ans=solve(g[i].p[k],g[j].p[l],n);if(ans > mmax) mmax = ans;}printf("Case %d: %d\n",ind++,mmax);}return 0;}
谁是谁生命的点缀。
