hdu 4063 Aircraft 计算几何+最短路

hdu 4063 Aircraft 计算几何+最短路

大家好,又见面了,我是全栈君。

易知最短路一定是以圆心或者两圆交点作为中间点到达的。所以把这些点拿出来建图跑最短路就够了。

如今的问题就是,给定两个点,是否能连边 add(a,b,dist(a,b))

题目要求,ab线段必须全然在圆上,所以能够求出ab线段和全部圆的全部交点,对于随意相邻两个交点,它们必处于同一个圆内,否则不可达。点的编号用map就够了(一開始我以为double有精度问题无法map。用两个longlong保存然后乘上1000000000,后来发现没问题。应该是这题都是整点,精度要求不高的原因吧)

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <cmath>
#include <cstring>
using namespace std;
#define pi acos(-1.0)
#define eps 1e-10
int cmp(double x)
{
    if(fabs(x)<eps) return 0;
    if(x>0) return 1;
    return -1;
}
double sqr(double x)
{
    return x*x;
}
struct point
{
    double x,y;
    point(){};
    point(double a,double b):x(a),y(b){};
    void out()
    {
        printf("%lf %lf\n",x,y);
    }
    void input()
    {
        scanf("%lf%lf",&x,&y);
    }
    friend point operator +(const point &a,const point &b)
    {
        return point(a.x+b.x,a.y+b.y);
    }
    friend point operator -(const point &a,const point &b)
    {
        return point(a.x-b.x,a.y-b.y);
    }
    friend bool operator ==(const point &a,const point &b)
    {
        return cmp(a.x-b.x)==0&&cmp(a.y-b.y)==0;
    }
    bool operator <(const point &a) const
    {
        if(x==a.x) return y<a.y;
        return x<a.x;
    }
    friend point operator *(const point &a,const double &b)
    {
        return point(a.x*b,a.y*b);
    }
    friend point operator *(const double &a,const point &b)
    {
        return point(a*b.x,a*b.y);
    }
    friend point operator /(const point &a,const double &b)
    {
        return point(a.x/b,a.y/b);
    }
    double norm()
    {
        return sqrt(sqr(x)+sqr(y));
    }
};
double det(const point &a,const point &b)
{
    return a.x*b.y-a.y*b.x;
}
double dot(const point&a,const point &b)
{
    return a.x*b.x+a.y*b.y;
}
double dist(const point &a,const point &b)
{
    return (a-b).norm();
}
point rotate_point(const point &p,double A)
{
    double tx=p.x,ty=p.y;
    return point(tx*cos(A)-ty*sin(A),tx*sin(A)+ty*cos(A));
}
point rotate(const point &p,double cost,double sint)
{
    double x=p.x,y=p.y;
    return point(x*cost-y*sint,x*sint+y*cost);
}

pair<point,point> crosspoint(point ap,double ar,point bp,double br)
{
    double d=(ap-bp).norm();
    double cost = (ar*ar + d*d -br*br)/(2*ar*d);
    double sint=sqrt(1.0-cost*cost);
    point v=(bp-ap)/(bp-ap).norm()*ar;
    return make_pair(ap+rotate(v,cost,-sint),ap+rotate(v,cost,sint));
}
void circle_cross_line(point a,point b,point o,double r,point ret[],int &num) {
    double x0 = o.x ,y0 = o.y;
    double x1 = a.x, y1 = a.y;
    double x2 = b.x, y2 = b.y;
    double dx = x2-x1, dy = y2-y1;
    double A = dx*dx+dy*dy;
    double B = 2*dx*(x1-x0) + 2*dy*(y1-y0);
    double C = sqr(x1-x0) + sqr(y1-y0)-sqr(r);
    double delta = B*B-4*A*C;
    if( cmp(delta) >= 0) {
        double t1 = (-B - sqrt(delta)) / (2*A);
        double t2 = (-B + sqrt(delta)) / (2*A);
        if(cmp(t1-1)<=0 && cmp(t1)>=0)
        ret[num++] = point(x1+t1*dx,y1+t1*dy);
        if(cmp(t2-1) <=0 && cmp(t2)>=0)
        ret[num++] = point(x1+t2*dx,y1+t2*dy);
    }
}
struct rad
{
    point c;
    double r;
}ra[300];
int n;
map<point,int> mp;
int ID;
int que[123456];
point xx[100005];
struct node2
{
    int v,next;
    double w;
}e[123456];
int head[12345];
bool in[12345];
double d[12345];
int en;
void add(int a,int b,double c)
{
  //  printf("%d %d %lf\n",a,b,c);
    e[en].v=b;
    e[en].w=c;
    e[en].next=head[a];
    head[a]=en++;

    e[en].v=a;
    e[en].w=c;
    e[en].next=head[b];
    head[b]=en++;
}
void spfa(int st)
{
    queue<int> q;
    memset(in,0,sizeof(in));
    for(int i=1;i<=ID;i++) d[i]=1000000000;
    q.push(st);
    in[st]=1;
    d[st]=0;
    int tmp;
    while(!q.empty())
    {
        tmp=q.front();q.pop();
        in[tmp]=0;
        for(int i=head[tmp];~i;i=e[i].next)
        {
            if(d[e[i].v]>d[tmp]+e[i].w)
            {
                d[e[i].v]=d[tmp]+e[i].w;
                if(!in[e[i].v])
                {
                    in[e[i].v]=1;
                    q.push(e[i].v);
                }
            }
        }
    }
}
bool inra(point &x,point &y)
{
    for(int i=1;i<=n;i++)
    {
        if(dist(x,ra[i].c)<=ra[i].r+eps && dist(y,ra[i].c)<=ra[i].r+eps)
        {
            return true;
        }
    }
    return false;
}
point my[12345];
bool cal(point &a,point &b)
{
    my[0]=a;
    int top=1;
    for(int i=1;i<=n;i++)
    {
        circle_cross_line(a,b,ra[i].c,ra[i].r,my,top);
    }
    my[top++]=b;
    sort(my,my+top);
    for(int i=1;i<top;i++)
    {
        if(!inra(my[i-1],my[i])) return false;
    }
    return true;
}
int main()
{
    int ca=1;
    int cas;
    scanf("%d",&cas);
    while(cas--)
    {
        mp.clear();
        scanf("%d",&n);
        ID=0;
        for(int i=1;i<=n;i++)
        {
            ra[i].c.input();
            scanf("%lf",&ra[i].r);
        }
        printf("Case %d: ",ca++);

        if(cal(ra[1].c,ra[n].c))    //冲榜都靠这个特判#_#
        {
            printf("%.4f\n",dist(ra[1].c,ra[n].c));
            continue;
        }
        en=0;
        memset(head,-1,sizeof(head));
        int top=0;
        for(int i=1;i<=n;i++)
        {
            mp[ra[i].c]=++ID;
            que[top++]=ID;
            xx[ID]=ra[i].c;
            for(int j=i+1;j<=n;j++)
            {
                if(dist(ra[i].c,ra[j].c)>(ra[i].r+ra[j].r)+0.0) continue;
                pair<point,point> tmp=crosspoint(ra[i].c,ra[i].r,ra[j].c,ra[j].r);
                if(mp[tmp.first]==0)
                {
                    mp[tmp.first]=++ID;
                    que[top++]=ID;
                    xx[ID]=tmp.first;
                }
                if(mp[tmp.second]==0)
                {
                    mp[tmp.second]=++ID;
                    que[top++]=ID;
                    xx[ID]=tmp.second;
                }
            }
        }
        mp[ra[n].c]=++ID;
        que[top++]=ID;
        xx[ID]=ra[n].c;
        for(int i=0;i<top;i++)
        {
            for(int j=i+1;j<top;j++)
            {
                if(cal(xx[que[i]],xx[que[j]]))
                {
                    add(que[i],que[j],dist(xx[que[i]],xx[que[j]]));
                }
            }
        }
        spfa(1);

        if(d[ID]>=1000000000) puts("No such path.");
        else printf("%.4f\n",d[ID]);
    }
    return 0;
}
/*
99
2
0 0 1
2 0 1
2
0 0 1
4 1 2
4
-4 0 1
-1 0 2
1 0 2
4 0 1
3
-3 0 1
0 0 2
0 3 1
3
-3 0 1
0 0 2
-2 -1 1
3
-3 0 1
-2 -1 1
0 0 2
4
2 2 2
2 -2 2
-2 2 2
-2 -2 2
2
0 0 3
1 0 1
3
0 0 1
2 2 2
3 0 1
3
0 0 1
3 0 1
2 2 2

ans:
2.0000
No
8.0000
4.8284
1.4142
3.0000
6.8284
1.0000
3.0654
2.8284
*/

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116566.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 成员函数

    成员函数在C++中,允许在结构体中定义函数,该函数称为“成员函数”。描述形式如下:struct结构名{数据成员成员函数};例题:身高问题输入n个学生的信息,每个学生的信息包括姓名、身高、学号。变

  • 文本文件比对_文本文件格式有哪些

    文本文件比对_文本文件格式有哪些前提需要安装python的pandas包

  • spssχ2检验_spss交叉表分析方法与步骤 + SPSS卡方检验结果的阅读

    spssχ2检验_spss交叉表分析方法与步骤 + SPSS卡方检验结果的阅读spss中交叉分析主要用来检验两个变量之间是否存在关系,或者说是否独立,其零假设为两个变量之间没有关系。在实际工作中,经常用交叉表来分析比例是否相等。例如分析不同的性别对不同的报纸的选择有什么不同。spss交叉表分析方法与步骤:1、在spss中打开数据,然后依次打开:analyze–descriptive–crosstabs,打开交叉表对话框2、将性别放到行列表,将对读物的选择变量放到列,这样…

  • 1. Pycharm新建项目[通俗易懂]

    1. Pycharm新建项目[通俗易懂]1.创建Python项目File–newproject(Location选择项目的位置,最后可以加上文件的名字,如Project1),选择好位置后,点击创建,完成项目的创建。2.创建python项目右键选择项目名称(Project1)的文件夹,–new–pythonfile,给文件起名字(如first)3.文件运行写完项目后,单击右键,选择run‘first’4.设置自己的起始模板file–setting–editer–fileandcodetemplates–pyt

    2022年10月29日
  • jar包与war包的区别

    jar包与war包的区别ar包:对于学习java的人来说应该并不陌生。我们也经常使用也一些jar包。其实jar包就是java的类进行编译生成的class文件就行打包的压缩包而已。里面就是一些class文件。当我们自己使用maven写一些java程序,进行打包生成jar包。同时在可以在其他的工程下使用,但是我们在这个工程依赖的jar包,在其他工程使用该jar包也要导入。这是jar的里面的class文件war包:其实就是一个web程序进行打包便于部署的压缩包,里面包含我们web程序需要的一些东西,其中包括web.xml的配

  • 闭关六个月整理出来的微机原理知识点(特别适用河北专接本)

    闭关六个月整理出来的微机原理知识点(特别适用河北专接本)笔者准备过程中的总结,是通过填空题,简答题等等总结出来的如有不足,还望大佬们指教A14运算器和控制器又称为中央处理器(CPU)。计算机由运算器控制器存储器输入设备输出设备五大部分组成。根据传送的信息类型,系统总线可以分为三类:数据总线地址总线控制总线8086CPU由总线接口部件BIU执行部件EU组成。半导体存储器按存取方式不同,分为读写存储器RAM只读存储器ROM。读写存储器RAM指可以随机地、个别地对任意一个存储单元进行读写的存.

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号