Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

题意看错了,疯掉。。。。 原来求的是最远的X,我求成了距离。。。。

Posted by bloodmary at 2008-07-10 19:24:22 on Problem 1039
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator