HDU 6097---Mindis(二分)
2018-06-17 22:04:53来源:未知 阅读 ()
题目链接
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.
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
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.
#include <iostream> #include <stdio.h> #include <math.h> #include <algorithm> using namespace std; const double eps = 1e-10; 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 = 0; sz = fread(buf, 1, MX, stdin); } inline bool read(int &t) { while(c < sz && buf[c] != '-' && (buf[c] < '0' || buf[c] > '9')) c++; if(c >= sz) return false; bool flag = 0; if(buf[c] == '-') flag = 1, c++; for(t = 0; c < sz && '0' <= buf[c] && buf[c] <= '9'; c++) t = t * 10 + buf[c] - '0'; 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=0; i<30; 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=1; 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=0; } if(flag==0) Rb=mid; else Lb=mid; } printf("%.10f\n",sqrt(a)*2.0); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- HDU-2955-Robberies(0-1背包) 2020-03-30
- hdu1455 拼木棍(经典dfs) 2020-02-29
- anniversary party_hdu1520 2020-02-16
- hdu1062 text reverse 2020-01-27
- hdu4841 2020-01-26
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash