T9的空间

You will never walk alone!

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  69 随笔 :: 0 文章 :: 28 评论 :: 0 Trackbacks

这个题要自己亲手画一画图,举个例子在纸上画一画,例如正方形,你会发现题目要求的是凸包的周长+圆的周长,下面是我的CODE,作为笔记。

 1/*
 2  Name: pku1113 
 3  Copyright: ccnu
 4  Author:Torres 
 5  Date: 11-08-08 12:04
 6  Description: 凸包 
 7*/

 8#include<iostream>
 9#include<cmath>
10#include<algorithm>
11using namespace std;
12const double pi=acos(-1.0);
13typedef struct point{
14    double x,y;
15    point(double x=0,double y=0)
16    {this->x=x;this->y=y;}
17}
point;
18int n,r;
19point p[1005],ch[1005];
20int top;
21
22//p0p1 crossmul p0p2
23double cross(point p0,point p1,point p2)
24{return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);}
25
26double dist(point a,point b)
27{return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
28
29double area(point a,point b)
30{return fabs(a.x*b.y-a.y*b.x);}
31
32bool cmp(point a,point b)
33{
34    double re=cross(p[0],a,b);
35    if(re>0)return true;
36    else if(!re&&dist(p[0],a)>dist(p[0],b))
37        return true;
38    else return false;
39}

40
41int main()
42{
43    int i,j;
44    double sum=0;
45    scanf("%d%d",&n,&r);
46    for(i=0;i<n;i++)
47        scanf("%lf%lf",&p[i].x,&p[i].y);
48    j=0;
49    for(i=1;i<n;i++)
50        if(p[i].y<p[j].y||p[i].y==p[j].y&&p[i].x<p[j].x)
51            j=i;
52    swap(p[0],p[j]);
53    sort(p+1,p+n,cmp);
54    ch[0]=p[0];ch[1]=p[1];ch[2]=p[2];top=2;
55    for(i=3;i<n;i++){
56        while(cross(ch[top-1],p[i],ch[top])>=0)
57        {
58            top--;
59            if(top==1)break;
60        }

61        ch[++top]=p[i];
62    }

63    for(i=0;i<
64        top;i++)
65        sum+=sqrt(dist(ch[i],ch[i+1]));
66    sum+=2*pi*r+sqrt(dist(ch[top],ch[0]));
67    printf("%.0lf\n",sum);
68    return 0;
69}

70
posted on 2008-09-07 12:57 Torres 阅读(336) 评论(0)  编辑 收藏 引用 所属分类: Computation Geometry

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理