HDU 6097---Mindis(二分)

时间:2022-09-24 12:40:17

题目链接

Problem Description
The center coordinate of the circle C is O, the coordinate of O is (0,0) , and the radius is r.
P and Q are two points not outside the circle, and PO = QO.
You need to find a point D on the circle, which makes PD+QD minimum.
Output minimum distance sum.
 
Input
The first line of the input gives the number of test cases T; T test cases follow.
Each case begins with one line with r : the radius of the circle C.
Next two line each line contains two integers x , y denotes the coordinate of P and Q.

Limits
T≤500000
−100≤x,y≤100
1≤r≤100

 
Output
For each case output one line denotes the answer.
The answer will be checked correct if its absolute or relative error doesn't exceed 10−6.
Formally, let your answer be a, and the jury's answer be b. Your answer is considered correct if |a−b|max(1,b)≤10−6.
 
Sample Input
4
4
4 0
0 4 
4
0 3
3 0
4
0 2
2 0
4
0 1
1 0
 
Sample Output
5.6568543
5.6568543
5.8945030
6.7359174
 
题意:有一个圆,圆心在原点,输入半径 r ,圆内有两个点P , Q 到圆心距离相同,现在求在圆上找一点M,使得PM+QM最小?
 
思路:
          HDU  6097---Mindis(二分)  HDU  6097---Mindis(二分)HDU  6097---Mindis(二分)
      对于圆内的两个点 P 和 Q ,如果以其作为椭圆两个焦点,由图一可以看到:当椭圆顶点与圆相切时 , 圆与椭圆会有三个焦点,而椭圆上的点到P、Q的距离和是定值。那么可以缩小椭圆,接下来会有四个交点,继续缩小椭圆,得到图二,椭圆与圆只有两个交点,因为椭圆外的点到两个焦点的距离和大于2a,而椭圆上的点到两个焦点的距离和为2a,。在图2中,除了两个交点外,其余圆上点均在椭圆外,所以这时的交点到P、Q两点的距离和最小,等于2a。
      如何找到这个相切的椭圆呢?二分解决。
      具体:由P、Q两个焦点,我们可以确定c=PQ/2 ,  现在如果再给出一个b值那么就能确定这个椭圆了,而b值越大椭圆越大,b值越小椭圆越小,所以我们要找到如图2所示,相切只有两个焦点时的b值,那么我们需要找的就是圆和椭圆相交时最小的b。我们可以求出图3中所示的 h 和 R -h ,那么椭圆的方程为:x^2/a^2 + (y-h)^2/b^2 = 1 ( 这个方程是PQ平行于X轴时的,但PQ不平行于X时也不影响,我们只是用它判断是否与圆相交 ) 圆:x^2 + y^2 =R^R ,    并且b>0(显然),b<R-h ,所以在(0,R-h) 二分查找b。
 
代码如下:
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
const double eps = 1e-;
double dis(double x1,double y1,double x2,double y2 )
{
return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}
namespace IO {
const int MX = 4e7; //1e7占用内存11000kb
char buf[MX]; int c, sz;
void begin() {
c = ;
sz = fread(buf, , MX, stdin);
}
inline bool read(int &t) {
while(c < sz && buf[c] != '-' && (buf[c] < '' || buf[c] > '')) c++;
if(c >= sz) return false;
bool flag = ; if(buf[c] == '-') flag = , c++;
for(t = ; c < sz && '' <= buf[c] && buf[c] <= ''; c++) t = t * + buf[c] - '';
if(flag) t = -t;
return true;
}
} int main()
{
IO::begin();
int T;
double R,x1,x2,y1,y2;
double x3,y3;
double A,B,C,dt,ans1,ans2;
//cin>>T;
IO::read(T);
while(T--)
{
//scanf("%lf%lf%lf%lf%lf",&R,&x1,&y1,&x2,&y2);
int xr, xx1, xx2, yy1, yy2;
IO::read(xr);
IO::read(xx1);
IO::read(yy1);
IO::read(xx2);
IO::read(yy2);
R = xr;
x1 = xx1;y1 = yy1;x2 = xx2;y2 = yy2;
double c=dis(x1,y1,x2,y2)*0.5;
c=c*c;
x3=(x1+x2)*0.5;
y3=(y1+y2)*0.5;
double h=dis(x3,y3,0.0,0.0);
//cout<<h<<endl;
double Rb=R-h;
double Lb=0.0,b,a,mid; for(int i=; i<; i++)
{
mid=(Lb+Rb)*0.5;
b = mid;
b=b*b;
a=c+b;
A=a-b;
B=2.0*a*h;
C=b*R*R+a*h*h-a*b;
dt=B*B-4.0*A*C;
int flag=;
if(dt>=-eps)
{
ans1=(-B+sqrt(B*B-4.0*A*C))*0.5/A;
ans2=(-B-sqrt(B*B-4.0*A*C))*0.5/A;
ans1=ans1*ans1;
ans2=ans2*ans2;
if(R*R-ans1>=-eps||R*R-ans2>=-eps)
flag=;
}
if(flag==)
Rb=mid;
else
Lb=mid;
}
printf("%.10f\n",sqrt(a)*2.0); }
return ;
}

HDU 6097---Mindis(二分)的更多相关文章

  1. 2017多校第6场 HDU 6097 Mindis 计算几何,圆的反演

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6097 题意:有一个圆心在原点的圆,给定圆的半径,给定P.Q两点坐标(PO=QO,P.Q不在圆外),取圆 ...

  2. hdu 6097 Mindis&lpar;数学几何,圆心的反演点&rpar;

    Mindis Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Subm ...

  3. 2017ACM暑期多校联合训练 - Team 6 1002 HDU 6097 Mindis (数学)

    题目链接 Problem Description The center coordinate of the circle C is O, the coordinate of O is (0,0) , ...

  4. HDU 6097 Mindis &lpar;计算几何&rpar;

    题意:给一个圆C和圆心O,P.Q是圆上或圆内到圆心距离相等的两个点,在圆上取一点D,求|PD| + |QD|的最小值 析:首先这个题是可以用三分过的,不过也太,.... 官方题解: 很不幸不总是中垂线 ...

  5. UVA 10816 &plus; HDU 1839 Dijstra &plus; 二分 (待研究)

    UVA 题意:两个绿洲之间是沙漠,沙漠的温度不同,告诉起点,终点,求使得从起点到终点的最高温度最小的路径,如果有多条,输出长度最短的路径: 思路:用最小费用(最短路径)最大流(最小温度)也能搞吧,但因 ...

  6. hdu 2413&lpar;最大匹配&plus;二分)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2413 思路:由于要求最少的时间,可以考虑二分,然后就是满足在limit时间下,如果地球战舰数目比外星战 ...

  7. HDU 5884 Sort &lpar;二分&rpar;

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5884 nn个有序序列的归并排序.每次可以选择不超过kk个序列进行合并,合并代价为这些序列的长度和.总的 ...

  8. hdu 1281棋盘游戏&lpar;二分匹配&rpar;

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1281   Problem Description 小希和Gardon在玩一个游戏:对一个N*M的棋盘, ...

  9. HDU 1025 DP &plus; 二分

    题目:http://acm.hdu.edu.cn/showproblem.php?pid=1025 求最长递增子序列,O(n^2)的复杂度超时,需要优化为O(n*logn) f[i]存储长度为i的最小 ...

  10. hdu 2289 要二分的杯子

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2289 大意是 一个Cup,圆台形,给你它的顶部圆的半径,底部圆的半径,杯子的高度,和此时里面装的水的体 ...

随机推荐

  1. MyISAM 和InnoDB 的区别&period;&lpar;存储&comma;索引&comma; 事务&comma; 锁&rpar;

    MyISAM类型的表强调的是性能,但是不支持事务.及外部键等高级功能. MySQL默认采用的是MyISAM. MyISAM不支持事务,而InnoDB支持.InnoDB的AUTOCOMMIT默认是打开的 ...

  2. 我的Sharepoint母版页的使用

    在Sharepoint 2010母版页文件夹里面,有一个叫v4.master的母版页文件. 在它的基础上修改成想要的母版页.我们用最少的修改完成我们想要的效果. 我们有时是要这样的一个母版页,顶部Ri ...

  3. 【BZOJ】2078&colon; &lbrack;POI2004&rsqb;WYS

    题意: 给n个互不相交的多边形(边均平行于坐标轴),问最大深度.深度的定义是,若多边形A被多边形B包含,则\(dep[A]=max(dep[B])+1\).坐标系的深度为0.(n<=40000, ...

  4. Java笔记&lpar;十七&rpar;&hellip&semi;&hellip&semi;异常

    异常概述 异常是什么 是对问题的描述,将问题进行对象的封装 异常体系 Throwable |---Error |---Exception |---RuntimeException 异常体系的特点 异常 ...

  5. C&num; Unity游戏开发——Excel中的数据是如何到游戏中的 (一)

    引言 现在做游戏开发的没有几个不用Excel的,用的最多的就是策划.尤其是数值策划,Excel为用户提供强大的工具,各种快捷键,各种插件,各种函数.但是作为程序来说其实关注的不是Excel而是它最终形 ...

  6. &lbrack;NOI赛前训练&rsqb;——专项测试3&&num;183&semi;数学

    由于并不想写T1和T2的题解……所有只有T3的题解了. T3 由于内部题就只写题解了. 好吧,我是一点都不想写…… 说一下这zz题解哪里写错了吧…… ……不想写…… 就说一个吧…… $n-\frac{ ...

  7. ftp 上传和下载

    ftp 下载 #!/bin/bash #auth liwei #date DATE=$(date -d today +%Y%m%d) #data files path SRCDIR=/home/web ...

  8. linxu系统知识和简单命令

    Linux目录基本知识 / 根目录 /bin 存放必要的命令 (binary) /boot 存放内核以及启动所需的文件(引导/自引/启动/开机程序) /dev 存放设备文件 (devices) /et ...

  9. 02 Java 基础语法

    在开始 Java 基本语法之前,先说明 Java 程序的基本规范: 大小写敏感,例如 Person 和 person 是不同的 类名首字母大写,如果类名由多个单词组成,每个单词首字母都大写,例如 He ...

  10. 2017-10-15 NOIP模拟赛

    Stack #include<iostream> #include<cstdio> #define mod 7 using namespace std; ][],n; int ...