首页 > 代码库 > poj3924
poj3924
题目：给定一个起点（xw1, yw1）,直线经过(xw2, yw2)，速度为vw无限运动的点，还有一个起点(xt1, yt1),终点(xt2, yt2),并且在以vt速度在两者往返运动，求两者在运动中的最近距离。。如果小于给定的dl，输出Dangerous，大于du输出Miss，否则输出perfect。。
思路：
ACM2008北京赛区的计算几何题，也是dyf神犇violet系列的一道题。。
思路不是很难，以xw点为参考系，那么题目就变成了求某个点及一些折线的最近距离。。
而且这些折线可以分成两组平行线段，每组可以分别求。
至于怎么求，可以用dyf神犇的数学方法。。（可能我太弱了，写完后一直错挑了半天就直接弃疗了）
我最后用的是直接三分线段，写起来好写一点。。
有什么不明白的可以看dyf博客。。写的很清楚。。
code：
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<algorithm> 7 #include<string> 8 #include<map> 9 #include<set> 10 #include<vector> 11 #include<queue> 12 #include<stack> 13 #include<ctime> 14 #include<utility> 15 #define M0(x) memset(x, 0, sizeof(x)) 16 #define eps 1e-8 17 #define pi acos(-1.0) 18 using namespace std; 19 inline int sgn(const double& x){ 20 return (x > eps) - (x < -eps); 21 } 22 struct point{ 23 double x, y; 24 point(){} 25 point(double _x, double _y):x(_x), y(_y){} 26 void input(){ 27 scanf("%lf%lf", &x, &y); 28 } 29 double len()const{ 30 return sqrt(x * x + y * y); 31 } 32 point trunc(double l)const{ 33 double r = l / len(); 34 return point(r * x, r * y); 35 } 36 point rotate_left()const{ 37 return point(-y, x); 38 } 39 point operator-(const point& p1)const{ 40 return point(x - p1.x, y - p1.y); 41 } 42 point operator+(const point& p1)const{ 43 return point(x + p1.x, y + p1.y); 44 } 45 bool operator==(const point& p1)const{ 46 return sgn(x - p1.x) == 0 && sgn(y - p1.y) == 0; 47 } 48 double operator*(const point& p1)const{ 49 return x * p1.y - y * p1.x; 50 } 51 double operator^(const point& p1)const{ 52 return x * p1.x + y * p1.y; 53 } 54 point operator*(const double& l) const{ 55 return point(x *l , y * l); 56 } 57 void out(){ 58 printf("%.2f %.2f\n", x, y); 59 } 60 } p[10], p2[10], v[10], zero(0, 0); 61 double di, du, vnow; 62 63 double get_distance(const point &p, const point &p1, const point &p2){ 64 if (sgn((p2 - p1) ^ (p - p1)) <= 0) return (p - p1).len(); 65 if (sgn((p1 - p2) ^ (p - p2)) <= 0) return (p - p2).len(); 66 return fabs((p1 - p) * (p2 - p)) / (p1 - p2).len(); 67 } 68 69 void init(){ 70 p2[0].input(), scanf("%lf", &vnow); 71 v[0] =(p2[0]-p[0]).trunc(vnow); 72 p[1].input(), p2[1].input(), scanf("%lf", &vnow); 73 v[1] = (p2[1] - p[1]).trunc(vnow); 74 p[1] = p[1] - p[0], p2[1] = p2[1] - p[0]; 75 scanf("%lf%lf", &di, &du); 76 } 77 78 double gao(const point& p0,const point& p1, const point& p2){ 79 int l = 0, r = 0x3fffffff, ui, l1, r1; 80 point v = p2 - p0; 81 point p00, p11; 82 double dis1, dis2, ans = 1e20; 83 while (l + 1 < r){ 84 if (l + 2 >= r){ 85 ans = min(ans, get_distance(zero, p0 + v * l, p1 + v * l)); 86 ans = min(ans, get_distance(zero, p0 + v * r, p1 + v * r)); 87 if (l + 2 == r) 88 ans = min(ans, get_distance(zero, p0 + v * (l+1), p1 + v * (l+1))); 89 break; 90 } 91 ui = (r - l + 1) / 3; 92 l1 = l + ui, r1 = r - ui; 93 dis1 = get_distance(zero, p0 + v * l1, p1 + v * l1); 94 dis2 = get_distance(zero, p0 + v * r1, p1 + v * r1); 95 if (dis1 < dis2) r = r1; 96 else l = l1; 97 98 } 99 return ans;100 }101 102 void solve(){103 point v1 = v[1] - v[0], v2 = (v[1] + v[0]) * (-1);104 double t = (p2[1] - p[1]).len() / vnow;105 point p0 = p[1], p1 = p0 + v1 * t, p3 = p1 + v2 * t, p4 = p3 + v1 * t;106 // p0.out(), p1.out(), p3.out(), p4.out();107 double ans = gao(p0, p1, p3);108 ans = min(gao(p1, p3, p4), ans); 109 if (ans < di - eps) puts("Dangerous");110 else if (ans > du + eps) puts("Miss");111 else puts("Perfect");112 }113 114 int main(){115 while (scanf("%lf%lf", &p[0].x, &p[0].y) != EOF){116 init();117 solve();118 }119 return 0;120 }
poj3924
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。