HDU 3952 Fruit Ninja (직선 과 선분 교차 매 거)

HDU 3952 Fruit Ninja (직선 과 선분 교차 매 거)
http://blog.csdn.net/zxy_snow/article/details/6699215
제목:
       평면 적 으로 n 개의 돌출 다각형 을 주 고 직선 을 그리 면 최대 몇 개의 돌출 다각형 을 통과 할 수 있 는 지 물 어보 세 요. 조금 만 교차 하 더 라 도 계산 합 니 다.
분석:
       결론: 한 직선 이 가장 많은 수의 다각형 을 통과 했다 고 가정 하면 우 리 는 반드시 이 직선 을 먼저 평평 하 게 이동 시 켜 이 직선 이 다각형 개 수 를 가장 많이 통과 하 는 전제 에서 그 중의 한 다각형 과 만 1 시 (다른 다각형 과 의 친분 상황 은 상관 하지 않 음) 에 교차 하 게 한 다음 에 회전 시 켜 이 직선 과 다른 다각형 도 한 점 에 만 교차 하 게 할 수 있다.
       위의 결론 을 통 해 알 수 있 듯 이 우 리 는 서로 다른 다각형 의 두 점 을 매 거 한 다음 에 이 두 점 으로 구 성 된 직선 을 목표 직선 으로 삼 아 그것 이 도대체 몇 개의 다각형 과 교차 하 는 지 보면 된다.
       직선 과 다각형 이 교차 하 는 지 여 부 를 판단 하려 면 이 직선 이 다각형 의 한 선분 과 교차 하 는 지 판단 하면 된다. (주의: 여 기 는 직선 과 선분 이 교차 하여 판정 된다)
AC 코드:

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const double eps=1e-10;
const int maxn=10+5;
int dcmp(double x)
{
    if(fabs(x)<eps) return 0;
    return x<0?-1:1;
}

struct Point // 
{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
};
typedef Point Vector;
Vector operator-(Point A,Point B)
{
    return Vector(A.x-B.x,A.y-B.y);
}
double Cross(Vector A,Vector B)//    
{
    return A.x*B.y-A.y*B.x;
}
bool LineIntersectionSegment(Point a1,Point a2,Point b1,Point b2)//    a1a2     b1b2  
{
    double c1=Cross(b2-b1,a1-b1),c2=Cross(b2-b1,a2-b1);
    return dcmp(c1)*dcmp(c2)<=0;
}
struct Polygen //   
{
    Point p[maxn];
    int k;
}Poly[maxn];

int get_num(Point p1,Point p2,int n)//   p1p2        
{
    int sum=0;
    for(int i=0;i<n;++i)
    for(int j=0;j<Poly[i].k;++j)
    {
        Point s1=Poly[i].p[j];
        Point s2=Poly[i].p[(j+1)%Poly[i].k];
        if(LineIntersectionSegment(s1,s2,p1,p2))
        {
            ++sum;
            break;
        }
    }
    return sum;
}

int main()
{
    int T; scanf("%d",&T);
    for(int kase=1;kase<=T;++kase)
    {
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;++i)
        {
            scanf("%d",&Poly[i].k);
            for(int j=0;j<Poly[i].k;++j)
                scanf("%lf%lf",&(Poly[i].p[j].x),&(Poly[i].p[j].y) );
        }
        if(n==1)
        {
            printf("Case %d: 1
",kase);
            continue;
        }
        int ans=0;
        for(int i=0;i<n;++i)// i    
        for(int j=0;j<Poly[i].k;++j)//i     j  
        for(int k=i+1;k<n;++k)
        for(int l=0;l<Poly[k].k;++l)
        {
            Point p1=Poly[i].p[j],p2=Poly[k].p[l];
            ans=max(ans,get_num(p1,p2,n));
        }
        printf("Case %d: %d
",kase,ans);
    }
    return 0;
}