首页 > ACM题库 > HDU-杭电 > Hdu 1589 Stars Couple-计算几何[解题报告] C++
2013
12-12

Hdu 1589 Stars Couple-计算几何[解题报告] C++

Stars Couple

问题描述 :

Can you believe it? After Gardon had solved the problem, Angel accepted him! They were sitting on the lawn, watching the stars.
“I still can’t believe this!” Gardon said.
Angel smiled and said: “The reason why I love you does not rest on of who you are, but on who I am when I am with you.”
Gardon answered :”In my view, it’s not because I’m lonely and it’s not because it’s the Valentine’s Day. It’s because when you realize you want to spend the rest of your life with somebody, you want the rest of your life to start as soon as possible!”
“Watch the stars! How beautiful!”
“Just like your eyes!” Gardon replied.
Angel smiled again:” Did you hear about this: one star means one person. When two people fall in love, their stars will be always nearby.”
“So we are the nearest couple?”
Now there is the question. Can you point out which couple of stars is nearest? Besides, can you fingle out which couple are most distant?

输入:

Input contains serveral test cases. Each cases starts with a integer N (2<=N<=50,000). Then N lines follow. Each line have two integers Xi and Yi(-10^9<Xi,Yi<10^9), which show the position of one star.
The input will be ended with a integer 0.

输出:

For each case, print the distance of the nearest couple and the most distant couple.
Print a blank line after each case.

样例输入:

3
1 1
0 0
0 1
0

样例输出:

Case 1:
Distance of the nearest couple is 1.000
Distance of the most distant couple is 1.414
Hint

Hint

Please use scanf instead of cin.

陈海峰(计算几何大牛)给我推荐的一个计算几何的经典题目!
看到这个题目!我想不看解题报告!因为,找最近点对我有上海交大的模板!至于找最远点对!我的思路是将点集凸包化(Gram_Scan算法),显然最远点对一定在凸包上,之后在运行一个N^2的算法!而这里的N=50000!似乎会超时!
呵呵!错了!当然不会超时间了啊!因为凸包化之后的点集会很少的!运行一个N^2算不了什么 !所以整个题目的运行时间是NlogN!事实证明的想法是对的最后运行时间是
7 ecjtu2008TracyMcGrad 453MS 1048K 3395B C++ 2009-03-17 21:23:53
排名第七!
ecjtunh的时间是:
4 ecjtunh 265MS 660K 1750B G++ 2008-04-21 10:17:20
时间比我快!呵呵!大牛就是大牛!
我先来贴一下自己的AC代码!

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int M=50005;
typedef struct Point
{
double x;
double y;
}Point;
Point p[M];
Point pp[M];
bool bo[M];
int stack[M];//form 1 to t;
double dis(Point A,Point B)
{
return sqrt((B.x-A.x)*(B.x-A.x)+(B.y-A.y)*(B.y-A.y));
}
bool cmp(Point a,Point b)
{
if(a.x<b.x)
    return true;
if(a.x>b.x)
    return false;
if(a.y<b.y)
    return true;
return false;
}
double Xdet(Point A,Point B,Point C)
{
double x1,x2,y1,y2;
x1=B.x-A.x;
y1=B.y-A.y;
x2=C.x-A.x;
y2=C.y-A.y;
return x1*y2-x2*y1;//大于0在左手边,逆时针
}
//把点集凸包化Gram_Scan算法(使用水平序)
void Gram_Scan(Point *p,int &n)//p从1-n,把点集土包化
{
int i,t;
sort(p+1,p+1+n,cmp);
for(t=0,i=1;i<=n;i++)
{
    if(i>1&&p[i].x==p[i-1].x&&p[i].y==p[i-1].y)
      continue;
    p[++t]=p[i];
}
n=t;
t=0;
memset(bo+1,true,n*sizeof(bo[0]));
if(n>0)
{
    stack[++t]=1;
    bo[stack[t]]=false;
}
if(n>1)
{
    stack[++t]=2;
    bo[stack[t]]=false;
}
if(n>2)
{
    for(i=3;i<n;i++)
      if(bo[i]&&Xdet(p[stack[t-1]],p[stack[t]],p[i])>=0)
      {
        stack[++t]=i;
        bo[i]=false;
      }
      else
      {
        while(t>=2&&Xdet(p[stack[t-1]],p[stack[t]],p[i])<0)
        {
          bo[stack[t]]=true;
          t--;
        }
        stack[++t]=i;
        bo[stack[t]]=false;
      }
   for(i=n;i>=1;i--)
     if(bo[i]&&Xdet(p[stack[t-1]],p[stack[t]],p[i])>=0)
     {
       stack[++t]=i;
       bo[i]=false;
     }
     else
     {
       while(t>=2&&Xdet(p[stack[t-1]],p[stack[t]],p[i])<0)
       {
         bo[stack[t]]=true;
         t--;
       }
       stack[++t]=i;
       bo[stack[t]]=false;
     }
     t--;
}
for(i=1;i<=t;i++)
    pp[i]=p[stack[i]];
memcpy(p+1,pp+1,t*sizeof(Point));
n=t;
}
int n,o[M],on;
int dcmp(double a,double b)
{
    if(a-b<1e-10&&b-a<1e-10)
        return 0;
    if(a>b)
        return 1;
    return -1;
}
bool cmp1(const Point &a,Point &b)
{
    return dcmp(a.x,b.x)<0;
}
bool cmp2(const int&a,const int&b)
{
    return dcmp(p[a].y,p[b].y)<0;
}
double min(double a,double b)
{
    return a<b?a:b;
}
double search(int s,int t)
{
    int mid=(s+t)/2,i,j;
    double ret=1e300;
    if(s>=t)
        return ret;
    for(i=mid;i>=s&&!dcmp(p[i].x,p[mid].x);i--);ret=search(s,i);
    for(i=mid;i<=t&&!dcmp(p[i].x,p[mid].x);i++);ret=min(ret,search(i,t));on=0;
    for(i=mid;i>=s&&dcmp(p[mid].x-p[i].x,ret)<=0;i--)o[++on]=i;
    for(i=mid+1;i<=t&&dcmp(p[i].x-p[mid].x,ret)<=0;i++)o[++on]=i;
    sort(o+1,o+on+1,cmp2);
    for(i=1;i<=on;i++)
        for(j=1;j<=10;j++)
            if(i+j<=on)
                ret=min(ret,dis(p[o[i]],p[o[i+j]]));
    return ret;
}
int main()
{
    int n,i,count=0,j;
    double shortdis,longdis;
    while(scanf("%d",&n),n)
    {
        for(i=1;i<=n;i++)
            scanf("%lf%lf",&p[i].x,&p[i].y);
        sort(p+1,p+n+1,cmp1);
        shortdis=search(1,n);
        longdis=0;
        Gram_Scan(p,n);
        for(i=1;i<=n-1;i++)
            for(j=i+1;j<=n;j++)
                if(dis(p[i],p[j])>longdis)
                    longdis=dis(p[i],p[j]);
        printf("Case %d:\n",++count);
        printf("Distance of the nearest couple is %.3lf\n",shortdis);
        printf("Distance of the most distant couple is %.3lf\n\n",longdis);
    }
    return 0;
}
/*
3
1 1
0 0
0 1
0

Case 1:
Distance of the nearest couple is 1.000
Distance of the most distant couple is 1.414
*/

转自:http://hi.baidu.com/ecjtuqx/item/1a436ad68c26cbca1a72b4b0