栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

poj 1113 Wall

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

poj 1113 Wall

#include <iostream>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <math.h>#include <algorithm>using namespace std;#define maxn 1005struct point{    double x, y;} pnt[maxn], res[maxn];int n, l;bool mult(point sp, point ep, point op){    return (sp.x - op.x) * (ep.y - op.y) >= (ep.x - op.x) * (sp.y - op.y);}bool operator<(const point &l, const point &r){    return l.y < r.y || (l.y == r.y && l.x < r.x);}int graham(point pnt[], int n, point res[]){    int i, len, top =1;    sort(pnt, pnt + n);    if (n ==0)        return 0;    res[0] = pnt[0];    if (n ==1)        return 1;    res[1] = pnt[1];    if (n ==2)        return 2;    res[2] = pnt[2];    for (i =2; i < n; i++)    {        while (top && mult(pnt[i], res[top], res[top -1])) top--;        res[++top] = pnt[i];    }    len = top;    res[++top] = pnt[n -2];    for (i = n -3; i >=0; i--)    {        while (top != len && mult(pnt[i], res[top], res[top -1])) top--;        res[++top] = pnt[i];    }    return top;}double dis(point &p, point &q){    double x1 = p.x - q.x, y1 = p.y - q.y;    return sqrt(x1 * x1 + y1 * y1);}int main(){    scanf("%d%d", &n, &l);    for (int i =0; i < n; i++)        scanf("%lf%lf", &pnt[i].x, &pnt[i].y);    int tot = graham(pnt, n, res);    double ans = l *2*3.14159265;    for (int i =0; i < tot; i++)        ans += dis(res[i], res[(i +1) % tot]);    printf("%.0fn", ans);    return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/372432.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号