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

Re:老wa, 找不出问题 代码如下

Posted by newjunwei at 2008-05-04 10:11:40 on Problem 1039
In Reply To:老wa, 找不出问题 代码如下 Posted by:first at 2006-05-23 22:59:10
> 比较混乱 就是枚举,那位给我看下或者给个正确的代码
> 
> #include <iostream>
> #include <iomanip>
> #include <cmath>
> #include <string>
> using namespace std;
> 
> #define DMAX 10e30;
> 
> 
> struct CPoint
> {
>    double x, y;
> }  ;
> 
> CPoint up[20], dp[20];
> 
> int n;
> double ans;
> bool same(double d1, double d2)
> {
> 	 return fabs(d1 - d2) < 0.000000001;
> }
> int length(CPoint& p1, CPoint& p2, int lim)
> {
> 	int k;
> 	double s, s1;
> 	double d, d1;
> 	double x, y, xx;
> 	s = (p2.y - p1.y)/(p2.x - p1.x);
> 	d = p1.y - s*p1.x;
> 	for(k = 0; k < n; k ++)
> 	{
> 		y = s*up[k].x + d;
> 		if(!same(y, dp[k].y) && !same(y, up[k].y))
> 			if(y < up[k].y - 1 || y > up[k].y)
> 			         break;
> 	}
> 	if(k == n)
> 		return -1;
> 	if(k <= lim)
> 		return 0;
> 	if(k)
> 	{ 
> 		//直线方程 y = s1*x + d1 和 y = s*x + d的交点
> 		s1 = (up[k].y - up[k - 1].y)/(up[k].x - up[k - 1].x);
> 		d1 =  up[k - 1].y - s1*up[k - 1].x;
> 		x = (d - d1)/(s1 - s);	
> 		xx = - DMAX;
> 		if((x > up[k - 1].x && x < up[k].x) || same(x, up[k - 1].x)
> 			|| same(x, up[k].x))
> 		    xx = max(x, xx);
> 		d1 --; //管道的下边界
> 		x = (d - d1)/(s1 - s);
> 	    if((x > up[k - 1].x && x < up[k].x) || same(x, up[k - 1].x)
> 			|| same(x, up[k].x))
> 		      xx = max(x, xx);
> 		ans = max(xx, ans);
> 	}
> 	return 0;
> }
> 
> void solve()
> {
> 	int i, j;
> 	int sig;
> 	for(i = 0; i < n; i ++)
> 	  for(j = i + 1; j < n; j ++)
> 	  {	
> 		  {
> 		  sig = length(up[i], dp[j], j);
> 		  if(sig == -1)
> 		  {
> 			  cout << "Through all the pipe.\n";
> 			  return;
> 		  }
> 		  sig = length(dp[i], up[j], j);
> 		  if(sig == -1)
> 		  {
> 			  cout << "Through all the pipe.\n";
> 			  return;
> 		  }
> 		  }
> 	 }
>  	 cout << fixed << setprecision(2) << ans << endl;
> }
> 
> int  main()
> { 
> 
> 	int i;
> 	ans = - DMAX;
> 	while(cin >> n && n)
> 	{
> 		for(i = 0; i < n; i ++)
> 		{
> 			cin >> up[i].x >> up[i].y;
> 			dp[i].x = up[i].x;
> 			dp[i].y = up[i].y - 1;
> 		}
> 	    solve();
> 	}
> 	return 0;   
> }
> 
> 
> 
> 
> 	
> 
> 
> 
> 
> 		
> 
> 
> 

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