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

错在哪里?

Posted by liangjingtao at 2012-07-08 14:06:01 on Problem 1039
#include<cstdio>
#include<cstdlib>
#include<iostream>
#define maxint 214748364700.0
#define maxn 100
using namespace std;

struct point
{
  double x,y;
}pipe[maxn],p;

int n;
double thex,ans;
void init(){for (int i=1;i<=n;i++) scanf("%lf%lf",&pipe[i].x,&pipe[i].y);}

double inter(point p1,point p2,point p3,point p4)
{
  double a1,b1,c1,a2,b2,c2,x;
  a1=p1.y-p2.y;
  b1=p1.x-p2.x;
  c1=p1.y*b1-p1.x*a1;
  
  a2=p3.y-p4.y;
  b2=p3.x-p4.x;
  c2=p3.y*b2-p3.x*a2;
  
  x=(c1*b2-c2*b1)/(a2*b1-a1*b2);
  return x;
}

bool check(point p1,point p2)
{
  double a,b,c,ty;
  a=p1.y-p2.y;
  b=p1.x-p2.x;
  c=p1.y*b-p1.x*a;
  ty=(a*pipe[1].x+c)/b;
  if (ty<=pipe[1].y && ty>=pipe[1].y-1) return true;
}

double getx(point p1,point p2)
{
  int i;
  double a,b,c,y,x;
  a=p1.y-p2.y;
  b=p1.x-p2.x;
  c=p1.y*b-p1.x*a;
  for (i=1;i<=n-1;i++)
  {
    y=(a*pipe[i+1].x+c)/b;
    if (y>pipe[i+1].y)
    {
      return inter(p1,p2,pipe[i],pipe[i+1]);
    }else
    if (y<pipe[i+1].y-1)
    {
      point newp1,newp2; 
      newp1=pipe[i]; newp2=pipe[i+1]; 
      newp1.y--; newp2.y--;
      return inter(p1,p2,newp1,newp2);
    }
  }
  
  return maxint;
}

void work()
{
  int i,j; ans=-maxint;
  for (i=1;i<=n;i++) for (j=1;j<=n;j++) if (i!=j)
  {
    point a,b; a=pipe[i]; b=pipe[j]; b.y--;
    if (check(a,b)) 
      if ((thex=getx(a,b))>ans) ans=thex;
  }
    if (ans==maxint) printf("Through all the pipe.\n");
      else printf("%.2lf\n",ans);
}

int main()
{
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  while (scanf("%d",&n)!=EOF)
  {
    if (n==0) break;
    init();
    work();
  }
  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