| ||||||||||
| 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