1065. Frontier

http://acm.timus.ru/problem.aspx?space=1&num=1065
두 가지 상황 으로 나누다
1, M = = 0 의 경우 이때 임의의 세 개의 점 (불 공선) 을 매 거 하여 길 이 를 계산 하 는 것 이 가장 짧다.
2，M!=0  이 럴 때 임의의 점 에서 다른 점 까지 의 거 리 를 매 거 합 니 다. 예 를 들 어 i 에서 j 까지 의 거리 가 모든 M 점 이 i 에서 j 벡터 의 오른쪽 에 있다 면
    거 리 는 직접 구 할 수 있 습 니 다. 그렇지 않 으 면 잠시 무한대 이 고 플 로 이 드 로 최 단 로 를 구하 고 마지막 으로 가장 작은 순환 로 를 구 할 수 있 습 니 다.
코드:

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<map>

#include<vector>

#include<stack>

#include<set>

#include<map>

#include<queue>

#include<deque>

#include<algorithm>

#include<cmath>

#define LL long long

//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

const double eps=1e-9;

const int INF=0x3f3f3f3f;

const double FINF=1e12;

const int N=1005;

const int M=55;

int n,m;

int x[N+M],y[N+M];

double dist[M][M];

double Fdist(int i,int  j)

{

    return sqrt(1.0*(x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]));

}

int main()

{

    //freopen("data.in","r",stdin);

    cin>>n>>m;

    for(int i=0;i<n;++i)

    cin>>x[i]>>y[i];

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

    cin>>x[i]>>y[i];

    if(m==0)

    {

        double ans=FINF;

        for(int i=0;i<n;++i)

        for(int j=0;j<n;++j)

        for(int l=0;l<n;++l)

        if((x[j]-x[i])*(y[l]-y[i])-(x[l]-x[i])*(y[j]-y[i])!=0)

        ans=min(ans,Fdist(i,j)+Fdist(i,l)+Fdist(j,l));

        printf("%.2f
",ans);

        return 0;

    }

    for(int i=0;i<n;++i)

    for(int j=0;j<n;++j)

    dist[i][j]=FINF;

    for(int i=0;i<n;++i)

    {

        bool flag=true;

        for(int j=i+1;flag;++j)

        {

            if(j==n) j=0;

            if((i-j+n)%n==1) break;

            for(int l=n;l<n+m;++l)

            {

                if((x[j]-x[i])*(y[l]-y[i])-(x[l]-x[i])*(y[j]-y[i])>=0)

                {flag=false;break;}

            }

            if(flag)

            dist[i][j]=Fdist(i,j);

        }

    }

    for(int l=0;l<n;++l)

    for(int i=0;i<n;++i)

    for(int j=0;j<n;++j)

    if(dist[i][l]+dist[l][j]<dist[i][j])

    dist[i][j]=dist[i][l]+dist[l][j];

    double ans=FINF;

    for(int i=0;i<n;++i)

    ans=min(ans,dist[i][i]);

    printf("%.2f
",ans);

    return 0;

}