POJ1271 Nice Milk

2014.12.13 13:49 Sat| 0 visits oi_2015| 2015_刷题日常| Text

Translated by 16bitwar

如他所说,这个题意真的很不科学

Problem

Background

小 A 很喜欢吃面包。

Description

有一天,小 A 坐在家里没事干,忽然想到了冰箱中一片面包。小 A 吃面包非常有经验。依照他的经验,面包片蘸牛奶吃才最好吃,但是为了让面包片变得不是太软,小 A 只能蘸固定的次数。他拿出了那片面包,可是那片面包并不是正常的面包的样子,而是一个凸多边形的面包片。他还有一桶牛奶,但是牛奶剩下的不多了,只有深度为 h 的牛奶在桶里。这让小 A 犯了难,如何才能在固定的次数内让面包蘸上牛奶的面积最大呢?

Input

第一行三个数字,m,n,h,表示这个面包片是一个凸 m 边形,n 代表小 A 最多可以蘸 n 次,h 是一个实数,表示奶桶中牛奶的深度。

接下来 m 行,每行两个实数,按照逆时针给出这个面包的每个定点的坐标。

Output

一个实数,表示小 A 最多可以让面包片蘸到牛奶的面积。(保留两位小数)

Sample Input

4 2 1

1 0

3 0

5 2

0 4

Sample Output

7.4

数据范围和约定

注:本题十分不科学,请勿将这个题和现实生活中的事物联系起来。

做以下说明:

  1. 不计面包的厚度。
  2. 面包蘸牛奶之后形状和面积均不会变化。
  3. 假设桶口是无限大的,也就是多大的面包都能蘸到牛奶。
  4. 不要想换一个容器以增加牛奶的深度,小 A 没有别的容器了。
  5. 蘸牛奶之后牛奶不会减少。 对于 20%的数据,保证这个面包是一个正常的面包,也就是形状是正方形。 对于 100%的数据,m,n <= 20。

Solution

让我们来仔细看题:

  1. 不计面包的厚度
  2. 桶口是无限大的 因此,如果可以蘸牛奶,则应该输出整个面包片的面积。可是这么完美的想法竟然不能过样例【真是hentai啊……】

脑补一下如果蘸牛奶的话,在边上蘸是最优的,所以可转化成半平面交模型进行求解,即在凸多边形上画 n 条与边平行且距离为 h 的边,使得剩余多边形的面积最小。这时可以用 DFS 求得所有蘸牛奶的方法。这在时间上可以承受。此题便可以解决。

这个题可以解出来了,可是如何证明在边上蘸牛奶是最优的?我不会,可是这貌似是对的……

在POJ上交题须知:

  1. n 可能会大于 m 。
  2. n 可能会等于 0 。
  3. 这道题是多组数据。
  4. 判断 n 等于 0 也要读入所有的点。

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;
#define sqr(x) ((x)*(x))
#define dcmp(x) (fabs(x)<1e-10)
#define N 50

struct point
{
    double x,y;
    point(double _x=0.0,double _y=0.0):x(_x),y(_y) {}
    point operator +(const point &a) const
    {
        return point(x+a.x,y+a.y);
    }
    point operator -(const point &a) const
    {
        return point(x-a.x,y-a.y);
    }
    point operator *(const double a) const
    {
        return point(x*a,y*a);
    }
    friend double cross(const point &a,const point &b)
    {
        return a.x*b.y-a.y*b.x;
    }
    friend double dist(const point &a,const point &b)
    {
        return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
    }
    inline void read()
    {
        cin>>x>>y;
    }
};

struct line
{
    point p,v; double t;
    line() {}
    line(point _p,point _v):p(_p),v(_v)
    {
        t=atan2(v.y,v.x);
    }
    bool operator <(const line &a) const
    {
        return t<a.t;
    }
    friend bool left(const point &p,const line &l)
    {
        return cross(l.v,p-l.p)>=0;
    }
    friend point intersection(const line &a,const line &b)
    {
        return a.p+a.v*(cross(b.v,a.p-b.p)/cross(a.v,b.v));
    }
};

int m,n,head,tail;
double ans,small,h;
point p[N],vertex[N]; line deq[N],l[N],l1[N],l2[N];

bool half_plane_intersection(int tot)
{
    memcpy(l,l1,sizeof l);
    sort(l+1,l+tot+1);
    head=tail=0; deq[tail++]=l[1];
    for(int i=2;i<=tot;i++)
    {
        while(tail-head>=2&&!left(vertex[tail-1],l[i])) tail--;
        while(tail-head>=2&&!left(vertex[head+1],l[i])) head++;
        if(dcmp(l[i].t-deq[tail-1].t))
            deq[tail-1]=left(l[i].p,deq[tail-1])?l[i]:deq[tail-1];
        else deq[tail++]=l[i];
        if(tail-head>=2) vertex[tail-1]=intersection(deq[tail-2],deq[tail-1]);
    }
    while(tail-head>=2&&!left(vertex[tail-1],deq[head])) tail--;
    vertex[head]=intersection(deq[tail-1],deq[head]);
    return tail-head>2;
}

double get_area(point p[],int begin,int end)
{
    double re=0;
    for(int i=begin+1;i<=end-2;i++)
        re+=cross(p[i]-p[begin],p[i+1]-p[begin]);
    return re/2;
}

void dfs(int x,int deep)
{
    if(deep) l1[m+deep]=l2[x];
    if(deep==n)
    {
        if(half_plane_intersection(n+m))
            small=min(small,get_area(vertex,head,tail));
        else
            small=0;
        return;
    }
    for(int i=x+1;i<=m;i++)
        dfs(i,deep+1);
}

int main()
{
    while(cin>>m>>n>>h,m||n||h)
    {
        memset(l1,0,sizeof l1);
        memset(l2,0,sizeof l2);
        for(int i=1;i<=m;i++) p[i].read();
        if(n==0) {puts("0.00");continue;}
        n=min(n,m);
        small=ans=get_area(p,1,m+1);
        double xx;
        for(int i=2;i<=m;i++)
            l1[i]=line(p[i-1],p[i]-p[i-1]),
            xx=h/dist(p[i],p[i-1]),
            l2[i]=line(p[i-1]+point(-l1[i].v.y*xx,l1[i].v.x*xx),p[i]-p[i-1]);
        l1[1]=line(p[m],p[1]-p[m]);
        xx=h/dist(p[1],p[m]),
        l2[1]=line(p[m]+point(-l1[1].v.y*xx,l1[1].v.x*xx),p[1]-p[m]);
        dfs(0,0);
        cout<<fixed<<setprecision(2)<<ans-small<<endl;
    }
    return 0;
}