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

zoj 2074 Trip

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

zoj 2074 Trip

#include<iostream>#include<cstdio>#include<cmath>#include<string.h> #include<algorithm>using namespace std;enum {    SIZ = 30008,};const double MaxAng = 1e20;struct Node {int x;int y;double ang;    bool operator<(const Node&rhs)const{        if( fabs(ang - rhs.ang)<1e-9){ return x < rhs.x;        }        return ang < rhs.ang;    }};Node tree[SIZ];int num, top;int save[SIZ];int readIn(){int least = 0,i;    if(scanf("%d",&num) < 0) return 0;for(i=0;i<num;i++){        scanf("%d%d", &tree[i].x, &tree[i].y);if(tree[i].x < tree[least].x){least = i;}else if(tree[i].x == tree[least].x && tree[i].y < tree[least].y ){least = i;}}int t;t = tree[least].x; tree[least].x = tree[0].x; tree[0].x = t;t = tree[least].y; tree[least].y = tree[0].y; tree[0].y = t;tree[0].ang = 0;for(i=1;i<num;i++){tree[i].x -= tree[0].x;tree[i].y -= tree[0].y;if(tree[i].x ==0){if(tree[i].y > 0){tree[i].ang = MaxAng;} else {tree[i].ang = -MaxAng;}} else {tree[i].ang = tree[i].y;tree[i].ang /= tree[i].x;}}tree[0].x = tree[0].y = 0;sort(tree+1, tree+num);return num;}int direct(int a,int b,int c){return (tree[b].x - tree[a].x)*(tree[c].y - tree[a].y) -(tree[c].x - tree[a].x)*(tree[b].y - tree[a].y);}double dis(int a, int b){double x,y;x = tree[a].x - tree[b].x;y = tree[a].y - tree[b].y;x *= x;y *= y;x += y;return sqrt(x);}void fun(){if(num==1){printf("0.00n");return;}top = 0;save[top++] = 0;save[top++] = 1;for(int i=2;i<num;i++){while(direct(save[top-2],save[top-1],i) < 0){top--;}save[top++] = i;}    for(int i=1; i<top; i++){        tree[save[i]].x += tree[0].x;        tree[save[i]].y += tree[0].y;    }double ret = 0, t, o;    int a=0, b=0;    for(;a < top; a++){        o = dis(save[a], save[b]);        if(ret < o) ret = o;        t = dis(save[a], save[(b+1)%top]);        while(t > o){ o = t; if(ret < t) ret = t; b = (b+1)%top; t = dis(save[a], save[(b+1)%top]);        }    }printf("%.2lfn", ret);}int main(){while(readIn() > 0){fun();}return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/379550.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

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

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