Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
题意看错了,疯掉。。。。 原来求的是最远的X,我求成了距离。。。。In Reply To:偶都快吐血了,黑书上的题目今天死活写不过。。。 大牛,HELP~~~ Posted by:bloodmary at 2008-07-10 14:08:55 > #include <stdio.h> > #include <math.h> > > typedef struct { > double x, y; > }point; > int dblcmp (double d) //判断d的符号 > { > if (fabs (d) < 1e-6) return 0; > return (d > 0) ? 1 : -1; > } > void getline (point a, point b, double &k, double &t, double &c) > { //根据点a,b求直线kx+ty+c=0 > k = a.y - b.y; > t = b.x - a.x; > c = a.x*b.y - b.x*a.y; > return ; > } > int cal (double k, double t, double c, point a) > {//计算点a在直线kx+ty+c=0的上方还是下方还是直线上 > return dblcmp (k*a.x + t*a.y + c); > } > int n; > const int size = 21; > point up[size], down[size]; > double max; > void updata (double k, double t, double c, point a, point b) > { //更新最大值 > double k2, t2, c2; > getline (a, b, k2, t2, c2); > double xp = (t*c2 - t2*c) / (k*t2 - t*k2); > double dist; > dist = (xp - up[0].x) * sqrt ((k*k)/(t*t) + 1); > if (dist > max) max = dist; > return ; > } > bool judge (point a, point b) > { // 判断点a,b构成的直线是否能通过整条管道 > double k, t, c; > getline (a, b, k, t, c); > //判断光线能够从第一个通道口射入 > if (cal(k, t, c, up[0]) * cal(k, t, c, down[0]) > 0) return false; > int i; > //寻找第一个拐角,在这个拐角前,光线已穿越管壁 > for (i = 1; i < n; i++) > if (cal(k, t, c, up[i]) * cal(k, t, c, down[i]) > 0) break; > if (i == n) return true; > if (cal(k, t, c, up[i]) * cal(k, t, c, up[i-1]) <= 0) updata (k, t, c, up[i], up[i-1]); > if (cal(k, t, c, down[i]) * cal(k, t, c, down[i-1]) <= 0) updata (k, t, c, down[i], down[i-1]); > return false; > } > bool solve () > { > for (int i = 0; i < n; i++) > for (int j = 0; j < n; j++){ > if (i == j) continue; > if (judge (up[i], down[j])) return true; > } > return false; > } > > int main () > { > // freopen ("in.txt", "r", stdin); > while (scanf ("%d", &n), n){ > for (int i = 0; i < n; i++){ > scanf ("%lf%lf", &up[i].x, &up[i].y); > down[i].x = up[i].x; down[i].y = up[i].y - 1; > } > max = 0; > if (solve ()) printf ("Through all the pipe.\n"); > else printf ("%.2f\n", max); > } > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator