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

zoj 2107 Quoit Design

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

zoj 2107 Quoit Design

# include<stdio.h># include<math.h>#include<stdlib.h>#define PI 0xffffffftypedef struct node{    double x,y;}Point;Point v[100005],X[100005];int n;int cmp(const  void *a,const void *b){    return ((Point *)a)->x > ((Point *)b)->x ? 1 : -1;}int cm(const void *a,const void *b){    return ((Point *)a)->y > ((Point *)b)->y ? 1 : -1;}double dist(Point s1, Point s2){    return sqrt((s1.x - s2.x)*(s1.x - s2.x) + (s1.y - s2.y)*(s1.y - s2.y));}double min(double a,double b){    return a > b ? b : a;}int min1(int a,int b){    return a > b ? b : a;}double Find_min(int i,int j){    int t,k,h;    double xx,delta;        if(j-i==1) return dist(X[j],X[i]);        else if(j-i==2)        { delta=PI; xx=dist(X[i],X[i+1]); if(xx<delta) {     delta=xx; } xx=dist(X[i],X[j]); if(xx<delta) {     delta=xx; } xx=dist(X[i+1],X[j]); if(xx<delta) {     delta=xx; } return delta;        }    k=(i+j)/2;    delta=min(Find_min(i,k),Find_min(k+1,j));    t=0;    for(h=k;h>=i;h--)    {        if(X[k+1].x - X[h].x < delta )        { t++; v[t]=X[h];        }        else  break;    }    for(h=k+1;h<=j;h++)    {        if(X[h].x - X[k].x < delta)        { t++; v[t]=X[h];        }        else break;    }    qsort(v+1,t,sizeof(v[1]),cm);    for(k=1;k<t;k++)    {        for(h=k+1;h<=min1(t,k+6);h++)        { if(v[h].y - v[k].y > delta) break; xx=dist(v[k],v[h]); if(xx<delta) {     delta=xx; }        }    }        return delta;}double closepoint(){    if(n==1) return 0;    qsort(X+1,n,sizeof(X[1]),cmp);    return Find_min(1,n);}int main(){    int i;    double ans;    while(scanf("%d",&n)!=EOF)    {        if(n==0) break;        for(i=1;i<=n;i++) scanf("%lf%lf",&X[i].x,&X[i].y);        ans=closepoint();        printf("%.2lfn",ans/2);    }    return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/379527.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

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

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