알 리 바 바 오픈 프 루트 닌 자 (평면 내 공선 이 가장 많은 다각형 개수 찾기)

만약 에 하나의 상황 공선 이 가장 많다 고 가정 하면 반드시 그 직선 을 평평 하 게 이동 하고 회전 시 켜 서 직선 이 그 중의 최소 2 개의 다 변 형 된 정점 을 통과 하 게 할 수 있 고 다각형 을 통과 하 는 성질 을 바 꾸 지 않 기 때문에 이런 다각형 만 매 거 하면 된다.
n 이 1 과 2 일 때 n 을 직접 출력 하면 됩 니 다. 처음에 n 의 범 위 를 잘못 보 았 고 1 의 상황 을 고려 하지 않 았 습 니 다. WA 는 여러 번 보 았 습 니 다.

#include <cstdio>

struct Node{
    int x,y;
}node[11][11];

struct Line{
    int A , B , C ;
}tmp;

int cnt[11];
int n;

bool is_through (int s)//judge the sth polygon
{
    for (int i=0 ; i<n ; ++i)
     for (int j=i+1 ; j<n ; ++j)
     {
         int x1,x2,y1,y2;
         x1=node[s][i].x,y1=node[s][i].y;
         x2=node[s][j].x,y2=node[s][j].y;
         if((tmp.A*x1+tmp.B*y1+tmp.C)*(tmp.A*x2+tmp.B*y2+tmp.C)<=0)return true;
     }
    return false ;
}

int getmax()
{
    int ans=0;
    int maxans=0;
    for (int i=0 ; i<n ; ++i)
      for (int p=0 ; p<cnt[i] ; ++p)
         for (int j=i+1 ; j<n ; ++j)
            for (int q=0 ; q<cnt[j] ; ++q)
             {
                 ans=0;
                 Node a=node[i][p],b=node[j][q];
                 tmp.A = b.y - a.y ;
                 tmp.B = a.x - b.x ;
                 tmp.C = b.x * a.y - a.x * b.y ;
                 for (int k=0 ; k<n ; ++k)
                 if(k!=i && k!=j)
                   if(is_through(k))++ans;
                 //printf("%d
",ans);
                 if(ans>maxans)maxans=ans;
             }
     return maxans;
}

int main ()
{
    int cas;
    //freopen ("Fruit.in","r",stdin);
    //freopen ("Fruit.txt","w",stdout);
    scanf("%d",&cas);
    for (int I=1 ; I<=cas ; ++I)
    {
        scanf("%d",&n);
        for (int i=0 ; i<n ; ++i)
        {
            scanf("%d",cnt+i);
            for (int j=0 ; j<cnt[i] ; ++j)
            {
                scanf("%d%d",&node[i][j].x,&node[i][j].y);
            }
        }
        if(n==1 || n==2){printf("Case %d: %d
",I,n); continue;}
        printf("Case %d: %d
",I,getmax()+2);
    }
    return 0;
}