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

提交快100次了 还是wa 到底是不是精度问题啊 求大侠教 附代码 g++

Posted by yongheng5871 at 2010-11-27 00:18:26 on Problem 1039
#include <iostream>
#include <fstream>
#include <algorithm>
#include <stdio.h>
using namespace std;
const int Max=25;
struct Point
{
    double x,y1,y2;
    bool operator<(const Point &a)const
    {
        return x<a.x;
    }
}point[Max];
int n;
int zero(double x)
{
    if (x<-0.000000001)return -1;
    if (x>0.000000001)return 1;
    return 0;
}
double chacheng(double x,double y,double i,double j)
{
    return x*j-y*i;
}
double fab(double x)
{
    if (zero(x)==-1)return -x;
    if (zero(x)==0)return 0;
    return x;
}
double jiaodian(double x,double y,int k,int flag,int i)
{
    double s1,s2,x1,y1,x2,y2;

    x1=point[i-1].x-point[k].x;
    x2=point[i].x-point[k].x;
    if (flag==1)
    {
        y1=point[i-1].y1-point[k].y1;
        y2=point[i].y1-point[k].y1;
    }
    else
    {
        y1=point[i-1].y1-point[k].y2;
        y2=point[i].y1-point[k].y2;
    }
    s1=chacheng(x,y,x1,y1);
    s2=chacheng(x,y,x2,y2);
    if (zero(s1*s2)>=0)
    {
        if (flag==1)
        {
            y1=point[i-1].y2-point[k].y1;
            y2=point[i].y2-point[k].y1;
        }
        else
        {
            y1=point[i-1].y2-point[k].y2;
            y2=point[i].y2-point[k].y2;
        }
        s1=chacheng(x,y,x1,y1);
        s2=chacheng(x,y,x2,y2);
    }
    if(zero(s1*s2)>=0)return point[i-1].x;
    s1=fab(s1);
    s2=fab(s2);
//    cout<<s1<<" "<<s2<<" "<<point[i-1].x<<" "<<point[i].x<<endl;
    return (s2*point[i-1].x+s1*point[i].x)/(s1+s2);
}
double test(double x,double y,int k,int flag)
{
    int i,x0,y1,y2;
    for (i=0;i<k;++i)
    {
        x0=point[k].x-point[i].x;
        if (flag==1)
        {
            y1=point[k].y1-point[i].y1;
            y2=point[k].y1-point[i].y2;
        }
        else
        {
            y1=point[k].y2-point[i].y1;
            y2=point[k].y2-point[i].y2;
        }
        if (zero(chacheng(x,y,x0,y1)*chacheng(x,y,x0,y2))<=0)
        {
            continue;
        }
        return point[0].x;
    }
    for (i=k+1;i<n;++i)
    {
        x0=point[k].x-point[i].x;
        if (flag==1)
        {
            y1=point[k].y1-point[i].y1;
            y2=point[k].y1-point[i].y2;
        }
        else
        {
            y1=point[k].y2-point[i].y1;
            y2=point[k].y2-point[i].y2;
        }
        if (zero(chacheng(x,y,x0,y1)*chacheng(x,y,x0,y2))<=0)
        {
            continue;
        }
        return jiaodian(x,y,k,flag,i);
    }
    return point[n-1].x;
}
int main()
{
//    freopen("in.txt","r",stdin);
    int i,j;
    while (scanf("%d",&n)!=EOF)
    {
        if (n==0)break;
        for (i=0;i<n;++i)
        {
            scanf("%lf%lf",&point[i].x,&point[i].y1);
            point[i].y2=point[i].y1-1;
        }
        sort(point,point+n);
        double x,y,temp0,ans=point[0].x;
        for (i=0;i<n;++i)
        {
            for (j=0;j<n;++j)
            {
                if(i==j)continue;
                x=point[i].x-point[j].x;
                y=point[i].y1-point[j].y2;
                if (i<j)
                {
                    temp0=test(x,y,j,2);
                }
                else
                {
                    temp0=test(x,y,i,1);
                }
//                cout<<temp0<<endl;
                if (temp0>ans)ans=temp0;
            }
        }
        if (ans>=point[n-1].x)printf("Through all the pipe.\n");
        else printf("%.2f\n",ans);
    }
    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