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
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

哪位大神救救我呀 给点数据吧!一直wa呀 有木有

Posted by 1011051119 at 2012-05-16 21:18:17 on Problem 1039
#include<iostream>
#include<cmath>
#include<string>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>

using namespace std;
const int N=25;
//const double K=1e-10;
struct node
{
    double x,y;
}uppoint[N];
struct node1
{
    double x,y;
}downpoint[N];
void point_of_intersection(double px,double py,double x1,double y1,double qx,double qy,double x2,double y2,double *k1)
{
    double K1=y1/x1;
    double K2=y2/x2;
    (*k1)=(qx*K2-qy+py-px*K1)/(K2-K1);
}
bool Can_keep_move(int l,int i,int j,double *k1)
{
    double x1=downpoint[j].x-uppoint[i].x;
    double y1=downpoint[j].y-uppoint[i].y;
    double x2=downpoint[l].x-uppoint[i].x;
    double y=(y1*x2)/x1+uppoint[i].y;
    if(y<=uppoint[l].y&&y>=downpoint[l].y)
    return true;
    if(l<max(i,j))
    return false;
    x2=uppoint[l].x-uppoint[l-1].x;
    double y2=uppoint[l].y-uppoint[l-1].y;
    if(y>uppoint[l].y)
    {
       point_of_intersection(uppoint[i].x,uppoint[i].y,x1,y1,uppoint[l].x,uppoint[l].y,x2,y2,k1);
    }
    else
    {
       point_of_intersection(uppoint[i].x,uppoint[i].y,x1,y1,downpoint[l].x,downpoint[l].y,x2,y2,k1);
    }
    return false;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF,n)
    {
        for(int i=1;i<=n;++i)
        {
            scanf("%lf %lf",&uppoint[i].x,&uppoint[i].y);
            downpoint[i].x=uppoint[i].x;
            downpoint[i].y=uppoint[i].y-1;
        }
        bool through=false;
        double ans=uppoint[1].x;
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=n;++j)
            {
                if(i==j)
                continue;
                int l,r;
                double lx,rx;
                for(l=max(i,j)-1;l>0;--l)
                {
                    if(!Can_keep_move(l,i,j,&lx))
                    break;
                }
                if(l!=0)
                continue;
                for(r=max(i,j)+1;r<=n;++r)
                {
                    if(!Can_keep_move(r,i,j,&rx))
                    break;
                }
                if(r==n+1)
                {
                    through=true;break;
                }
                else
                {
                    if(rx>ans)
                    ans=rx;
                }
            }
            if(through==true)
            break;
        }
        if(through==false)
        printf("%.2f\n",ans);
        else
        printf("Through all the pipe.\n");
    }
    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