| ||||||||||
| 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 | |||||||||
Re:老wa, 找不出问题 代码如下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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator