首页 > 代码库 > 2017多校第6场 HDU 6097 Mindis 计算几何,圆的反演
2017多校第6场 HDU 6097 Mindis 计算几何,圆的反演
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6097
题意:有一个圆心在原点的圆,给定圆的半径,给定P、Q两点坐标(PO=QO,P、Q不在圆外),取圆上一点D,求PD+QD的最小值。
解法:圆的反演。
很不幸不总是中垂线上的点取到最小值,考虑点在圆上的极端情况。
做P点关于圆的反演点P‘,OPD与ODP‘相似,相似比是|OP| : r。
Q点同理。
极小化PD+QD可以转化为极小化P‘D+Q‘D。
当P‘Q‘与圆有交点时,答案为两点距离,否则最优值在中垂线上取到。
时间复杂度 O(1)
也有代数做法,结论相同。
优秀的黄金分割三分应该也是可以卡过的。
分析可以看这个博客:http://blog.csdn.net/qq_34845082/article/details/77099332
#include <bits/stdc++.h> using namespace std; typedef long long LL; struct FastIO { static const int S = 1310720; int wpos; char wbuf[S]; FastIO() : wpos(0) {} inline int xchar() { static char buf[S]; static int len = 0, pos = 0; if(pos == len) pos = 0, len = fread(buf, 1, S, stdin); if(pos == len) exit(0); return buf[pos ++]; } inline unsigned long long xuint() { int c = xchar(); unsigned long long x = 0; while(c <= 32) c = xchar(); for(; ‘0‘ <= c && c <= ‘9‘; c = xchar()) x = x * 10 + c - ‘0‘; return x; } inline long long xint() { long long s = 1; int c = xchar(), x = 0; while(c <= 32) c = xchar(); if(c == ‘-‘) s = -1, c = xchar(); for(; ‘0‘ <= c && c <= ‘9‘; c = xchar()) x = x * 10 + c - ‘0‘; return x * s; } inline void xstring(char *s) { int c = xchar(); while(c <= 32) c = xchar(); for(; c > 32; c = xchar()) * s++ = c; *s = 0; } inline double xdouble() { bool sign = 0; char ch = xchar(); double x = 0; while(ch <= 32) ch = xchar(); if(ch == ‘-‘) sign = 1, ch = xchar(); for(; ‘0‘ <= ch && ch <= ‘9‘; ch = xchar()) x = x * 10 + ch - ‘0‘; if(ch == ‘.‘) { double tmp = 1; ch = xchar(); for(; ch >= ‘0‘ && ch <= ‘9‘; ch = xchar()) tmp /= 10.0, x += tmp * (ch - ‘0‘); } if(sign) x = -x; return x; } inline void wchar(int x) { if(wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0; wbuf[wpos ++] = x; } inline void wint(long long x) { if(x < 0) wchar(‘-‘), x = -x; char s[24]; int n = 0; while(x || !n) s[n ++] = ‘0‘ + x % 10, x /= 10; while(n--) wchar(s[n]); } inline void wstring(const char *s) { while(*s) wchar(*s++); } inline void wdouble(double x, int y = 8) { static long long mul[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000LL, 100000000000LL, 1000000000000LL, 10000000000000LL, 100000000000000LL, 1000000000000000LL, 10000000000000000LL, 100000000000000000LL}; if(x < -1e-12) wchar(‘-‘), x = -x; x *= mul[y]; long long x1 = (long long) floorl(x); if(x - floor(x) >= 0.5) ++x1; long long x2 = x1 / mul[y], x3 = x1 - x2 * mul[y]; wint(x2); if(y > 0) { wchar(‘.‘); for(size_t i = 1; i < y && x3 * mul[i] < mul[y]; wchar(‘0‘), ++i); wint(x3); } } ~FastIO() { if(wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0; } } io; const double eps = 1e-8; double getDis(double x, double y){ return sqrt(x*x+y*y); } double r,x1,y1,x2,y2; int main() { int T = io.xint(); while(T--) { r = io.xdouble(); x1 = io.xdouble(); y1 = io.xdouble(); x2 = io.xdouble(); y2 = io.xdouble(); double d0 = getDis(x1, y1); if(fabs(d0)<=eps){//p和q和原点重合 printf("%.8f\n", 2*r); continue; } double k = r*r/d0/d0;//用这个比例确定p和q的反演点 double x3=x1*k, x4=x2*k; double y3=y1*k, y4=y2*k; double mx=(x3+x4)/2.0,my=(y3+y4)/2.0; double ans; double d = getDis(mx, my); if(d <= r){//判断反演点和半径的关系 如果两个反演点的中点到圆心的距离小于半径 double dis = getDis(x3-x4,y3-y4); ans = dis*d0/r; } else{//其他的即是连线与圆相离时的状态 这时候的d点是p和q的反演点的连线的中垂线与圆的交点 double kk=r/d;//其他的即是连线与圆相离时的状态 这时候的d点是p和q的反演点的连线的中垂线与圆的交点 double smx = mx*kk, smy = my*kk; ans = 2*getDis(smx-x1,smy-y1); } printf("%.8f\n", ans); } return 0; }
2017多校第6场 HDU 6097 Mindis 计算几何,圆的反演
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。