T9的空间

You will never walk alone!

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  69 随笔 :: 0 文章 :: 28 评论 :: 0 Trackbacks
这个题意思很清楚,求50000个点中距离最大的两个点,并输出最大距离,普通的o(n^2)是过不了的,正确的做法应该是利用凸包graham-scan(o(nlogn))扫描法缩小点集,然后用一个旋转卡壳的的算法(o(n))求出凸多边形的直径,但是当我在写旋转卡壳的时候wa了,我疯了,换了一个普通的二重循环居然过了,数据不强,要是那50000个点都为凸包的顶点就惨了。
 1/*
 2  Name: pku2187
 3  Copyright: ccnu 
 4  Author: Torres  
 5  Date: 11-08-08 15:08
 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;
19point p[50005],ch[50005];
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
29bool cmp(point a,point b)
30{
31    double re=cross(p[0],a,b);
32    if(re>0)return true;
33    else if(!re&&dist(p[0],a)>dist(p[0],b))
34        return true;
35    else return false;
36}

37
38void graham(point a[])
39{
40    int i,j=0;
41    for(i=1;i<n;i++)
42        if(a[i].y<a[j].y||a[i].y==a[j].y&&a[i].x<a[j].x)j=i;
43    swap(a[0],a[j]);//找出左下点
44    sort(a+1,a+n,cmp);
45    ch[0]=a[0];ch[1]=a[1];ch[2]=a[2];top=2;
46    for(i=3;i<n;i++){
47        while(cross(ch[top-1],a[i],ch[top])>=0)
48        {
49            top--;
50            if(top==1)break;
51        }

52        ch[++top]=a[i];//试探
53    }

54}

55int main()
56{
57    int i,j;
58    int len=0;
59    scanf("%d",&n);
60    for(i=0;i<n;i++)
61        scanf("%lf%lf",&p[i].x,&p[i].y);
62    graham(p);
63    for(i=0;i<=top;i++)
64        for(j=0;j<=top;j++){
65            double temp=dist(ch[i],ch[j]);
66            if(len<temp)len=(int)temp;
67        }

68        printf("%d\n",len);
69    return 0;
70}

71
72

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

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理