uva 10641 (來當雷鋒的這回....)

uva 10641 (來當雷鋒的這回....)

#include
#include
#include
#include
using namespace std;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;

int n,m;
int f[100];
struct point{
    double x,y;
    point(double xx = 0,double yy = 0){
        this->x = xx;
        this->y = yy;
    }
    void read(){
        scanf("%lf%lf",&x,&y);
    }
}p[100];
struct Q{
    int l,r,c;
}q[1005];
bool judge(point pp,point p1,point p2){///向量叉積！判斷順逆時針時注意三個點的先後位置
    /// <0是就是第一個向量在第二個向量的逆時針方向；
    return ((p1.x-pp.x)*(p2.y-pp.y)-(p2.x-pp.x)*(p1.y - pp.y)) < -eps;
}
Q tra(point t,int c){
    Q ans;
    bool flag[100];
    memset(flag,false,sizeof(flag));
    for(int i = 0; i < n; i++){
        if(judge(t,p[i],p[i+1])){///判斷能不能照到這條邊
                                 ///（實際上判斷轉化成了照到點）；
            flag[i] = true;
        }
    }
    ///下面是處理得出的數據，保存下每個燈所能照到的最左端和最右端；
    if(flag[n-1]&&flag[0]){
        int left = n-1;
        while(flag[left-1]){left--;}
        int right = 0;
        while(flag[right+1]){right++;}
        ans.l = left;
        ans.r = right + n;
    }
    else{
        int left = 0,right = n-1;
        while(!flag[left]){left++;}
        while(!flag[right]){right--;}
        ans.l = left;
        ans.r = right;
    }
    ans.c = c;
    return ans;
}
bool solve()
{
    int ans = inf;
    for(int i = 0; i < n; i++){
        memset(f,inf,sizeof(f));
        f[i] = 0;
        for(int j = 0; j < n; j++){
            int r = i + j;///從第i個點開始往後數了j個；
                          ///多定義這麼一個層次，可以使狀態的轉移變得有序
            for(int k = 0; k < m; k++){
                if(q[k].l > r) continue;///當前點與該燈照亮的最左點之間有空隔，就不符合開始更新的條件；
                if(q[k].r < r) continue;///這是個剪枝，去掉也對；就是不再考慮不會成為最優解的情況；
                int now = min(q[k].r + 1, i + n);///根據區間右端點往後更新，但是一旦更新過了i+n就要將端點定為i+n；
                f[now] = min(f[now],f[r] + q[k].c);
            }
        }
        ans = min(ans,f[i+n]);
    }
    if(ans == inf) return false;
    printf("%d\n",ans);
    return true;
}
int main()
{
    while(scanf("%d",&n) != EOF){
        if(n == 0) break;
        for(int i = 0; i < n; i++){
            p[i].read();
        }
        p[n] = p[0];

        scanf("%d",&m);
        point temp;int c;
        for(int i = 0; i < m; i++){
            temp.read();
            scanf("%d",&c);
            q[i] = tra(temp,c);
        }

        if(!solve()) printf("Impossible.\n");
    }
    return 0;
}