注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ1209][HNOI2004]最佳包裹  

2015-06-02 21:21:31|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1209: [HNOI2004]最佳包裹

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 171  Solved: 64
[Submit][Status][Discuss]

Description

H公司生产了一种金属制品,是由一些笔直的金属条支撑起来的,金属条和别的金属条在交点上被焊接在了一起。现在由于美观需要,在这个产品用一层特殊的材料包裹起来。公司为了节约成本,希望消耗的材料最少(不计裁剪时的边角料的损失)。你的程序需要根据给定的输入,给出符合题意的输出:? 输入包括该产品的顶点的个数,以及所有顶点的坐标;? 你需要根据输入的计算出包裹这个产品所需要的材料的最小面积。? 结果要求精确到小数点后第六位。(四舍五入)

Input

第1行是一个整数n(4 <= n <= 100),表示顶点的个数;第2行到第n+1行,每行是3个实数xi,yi,zi,表示第i个顶点的坐标。每个顶点的位置各不相同。

Output

输出只有一个实数,表示包裹一个该产品所需的材料面积的最小值。

Sample Input

4 0 0 0 1 0 0 0 1 0 0 0 1

Sample Output

2.366025

Source

Solution

增量法。只存凸包的面。
把每条边拆成两个方向的单向边,每次添加一个点的时候标记一下这条边某侧的区域是否能被看见
如果对于一条边来说,一侧能被看见而另一侧不能被看见,那么这条边一定是下一个凸包上的边。

Code

/**************************************************************
    Problem: 1209
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:912 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
typedef double ld;
char ch,B[1<<15],*S=B,*T=B;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
#define isd(c) (c>='0'&&c<='9')
int bb;ld aa,ee;ld F(){
    while(ch=getc(),!isd(ch)&&ch!='-');ch=='-'?aa=bb=0:(aa=ch-'0',bb=1);
    while(ch=getc(),isd(ch))aa=aa*10+ch-'0';ee=1;
    if(ch=='.')while(ch=getc(),isd(ch))aa+=(ch-'0')*(ee*=0.1);return bb?aa:-aa;
}
ld G(){
    return (rand()-(1<<30))/1e21;
}
int n,i,j,t[2],vis[110][110],now,las,tmp;ld ans;
struct P{ld x,y,z;}p[110];
#define PP const P&
P operator-(PP a,PP b){return (P){a.x-b.x,a.y-b.y,a.z-b.z};}
P operator&(PP a,PP b){return (P){a.y*b.z-a.z*b.y,a.z*b.x-a.x*b.z,a.x*b.y-a.y*b.x};}
ld operator|(PP a,PP b){return a.x*b.x+a.y*b.y+a.z*b.z;}
ld len(PP a){return sqrt(a.x*a.x+a.y*a.y+a.z*a.z);}
#define ck(a,b,c) ((b-a)&(c-a))
struct Sfc{
    int a,b,c;P s;
    void up(int x,int y,int z){
        a=x,b=y,c=z,s=ck(p[x],p[y],p[z]);
    }
}q[2][310];
#define see(i,f) ((f.s|(p[i]-p[f.a]))>0)
#define ns q[las][j]
int main(){
    scanf("%d",&n);
    for(i=1;i<=n;i++)p[i]=(P){F()+G(),F()+G(),F()+G()};
    for(q[1][++t[1]].up(1,2,3),q[1][++t[1]].up(3,2,1),i=4;i<=n;i++){
        now=i&1,las=now^1,t[now]=0;
        for(j=1;j<=t[las];j++){
            if(tmp=see(i,ns),!tmp)q[now][++t[now]]=ns;
            vis[ns.a][ns.b]=vis[ns.b][ns.c]=vis[ns.c][ns.a]=tmp;
        }
        for(j=1;j<=t[las];j++){
            if(vis[ns.a][ns.b]&&!vis[ns.b][ns.a])q[now][++t[now]].up(ns.a,ns.b,i);
            if(vis[ns.b][ns.c]&&!vis[ns.c][ns.b])q[now][++t[now]].up(ns.b,ns.c,i);
            if(vis[ns.c][ns.a]&&!vis[ns.a][ns.c])q[now][++t[now]].up(ns.c,ns.a,i);
        }
    }
    for(now=n&1,i=1;i<=t[now];i++)ans+=len(q[now][i].s);
    printf("%lf\n",ans*0.5);
}
  评论这张
 
阅读(112)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018