加载中…
个人资料
JosiahChiu
JosiahChiu
  • 博客等级:
  • 博客积分:0
  • 博客访问:7,096
  • 关注人气:87
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

POJ PKU 1113 Graham 扫描法

(2010-07-20 10:51:16)
标签:

poj

pku

1113

it

分类: 计算几何

题目描述:和上题一样,朴素凸包

代码如下

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
#define size 1000
struct pint
{
    int x, y;
}x[size];
bool cmp(pint p1, pint p2)
{
    int temp = (p1.x - x[0].x) * (p2.y - x[0].y) - (p2.x - x[0].x) * (p1.y - x[0].y);
    if (temp == 0) return (p1.x >= min(x[0].x, p2.x) && p1.x <= max(x[0].x, p2.x));
    else return temp > 0;
}
bool CrossLeft(pint p1, pint p2, pint p3)//是否严格左转,共线不算左转
{
    return ((p3.x - p1.x) * (p2.y - p1.y) - (p2.x - p1.x) * (p3.y - p1.y)) < 0;
}
int ans[size], cnt, n, l;
void Graham()
{
    sort(x + 1, x + n, cmp);cnt = 0;
    ans[cnt++] = 0;ans[cnt++] = 1;
    for(int i = 2; i < n; i++)
    {
        while(cnt > 1 && !CrossLeft(x[ans[cnt - 2]], x[ans[cnt - 1]], x[i])) cnt--;
        ans[cnt++] = i;
    }
    ans[cnt++] = 0;
}
int tx, ty, tid;
int main()
{
    scanf("%d%d", &n, &l);
    tx = ty = 1000000;
    for(int i = 0; i < n; i++)
    {
        scanf("%d%d", &x[i].x, &x[i].y);
        if (x[i].y < ty || x[i].y == ty && x[i].x < tx)
        {
            tx = x[i].x, ty = x[i].y;
            tid = i;
        }
    }
    pint temp = x[tid];x[tid] = x[0];x[0] = temp;
    Graham();
    double re = 4 * acos(0.0) * l;
    for(int i = 0; i < cnt - 1; i++)
        re += sqrt((x[ans[i]].x - x[ans[i + 1]].x) * (x[ans[i]].x - x[ans[i + 1]].x) + (x[ans[i]].y - x[ans[i + 1]].y) * (x[ans[i]].y - x[ans[i + 1]].y) * 1.0);
    printf("%.0f\n", re);
    return 0;
}

0

阅读 收藏 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有