bzoj 1390: [Ceoi2008]Fence

Description

在一个大小为1000*1000的区域中，有n个固定点,m棵tree 。 现在你要建一个围栏来保护tree,建它的费用为你选用的固定点的个数 *20和 你没有圈进围栏的tree*111. 现在希望这个值越小越好. 3<=N<=100. 1<=M<=100

Input

第一行给出n,m 下面开始n行，给出固定的坐标 下面开始m行，给出tree的坐标

Output

输出最小费用

根据题目设定的参数，凡是可以围住的点都要围住，同bzoj1027可以转为最小环

#include<bits/stdc++.h>

struct pos{

    int x,y;

    void read(){

        scanf("%d%d",&x,&y);

    }

}ns[],ms[],cs[];

pos operator-(pos a,pos b){return (pos){a.x-b.x,a.y-b.y};}

int operator*(pos a,pos b){return a.x*b.y-a.y*b.x;}

bool operator<(pos a,pos b){return a*b<;}

int ans=,n,m,cp=;

bool in(pos w){

    for(int i=;i<cp;++i)if(cs[i-]<w&&w<cs[i]){

        return cs[i-]-w<cs[i]-w;

    }

    return ;

}

void mins(int&a,int b){if(a>b)a=b;}

int l[][];

char s[][];

int main(){

    scanf("%d%d",&n,&m);

    for(int i=;i<n;++i)ns[i].read();

    for(int i=;i<m;++i)ms[i].read();

    for(int i=;i<n;++i)if(ns[i].x<ns[].x)std::swap(ns[i],ns[]);

    pos p0=ns[];

    for(int i=;i<n;++i)ns[i]=ns[i]-p0;

    for(int i=;i<m;++i)ms[i]=ms[i]-p0;

    std::sort(ns+,ns+n);

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

        while(cp>=&&ns[i]-cs[cp-]<cs[cp-]-cs[cp-])--cp;

        cs[cp++]=ns[i];

    }

    int p=;

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

        if(!in(ms[i]))ans+=;

        else ms[p++]=ms[i];

    }

    m=p;

    if(p){

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

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

                l[i][j]=0x3f3f3f3f;

                if(i!=j){

                    bool is=;

                    pos d=ns[i]-ns[j];

                    for(int k=;k<m;++k)if(d<ms[k]-ns[j]){

                        is=;

                        break;

                    }

                    if(is)l[i][j]=;

                }

            }

        }

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

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

                for(int j=;j<n;++j)mins(l[i][j],l[i][k]+l[k][j]);

        for(int i=;i<n;++i)mins(l[][],l[i][i]);

        ans+=l[][]*;

    }

    printf("%d\n",ans);

    return ;

}