注册 登录  
 加关注

网易博客网站关停、迁移的公告:

将从2018年11月30日00:00起正式停止网易博客运营
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zxj015

 
 
 

日志

 
 

poj 2826 An Easy Problem?!  

2011-05-04 20:01:22|  分类: 计算几何 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

http://poj.org/problem?id=2826

由两条线段组成的容器,最多能装多少的雨量,雨水垂直下落。

下面三种情况是肯定不会积到雨的:

1、两条线段没有交点;

2、有一条水平;

3、如图所示的情况(很容易被忽略):

poj 2826 An Easy Problem?! - 某年某月 - zxj015的博客

 

 

下面的代码G++一直WA,后来在discuss在看到提示,改为C++,居然AC了,汗。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#define eps 1e-9
using namespace std;
struct point
{
 double x,y;
}p[4];
double multi(point p0,point p1,point p2)
{
 return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
bool is(point s1,point e1,point s2,point e2)
{
 return (max(s1.x,e1.x)-min(s2.x,e2.x)>-eps)&&
   (max(s2.x,e2.x)-min(s1.x,e1.x)>-eps)&&
   (max(s1.y,e1.y)-min(s2.y,e2.y)>-eps)&&
   (max(s2.y,e2.y)-min(s1.y,e1.y)>-eps)&&
   (multi(s1,s2,e1)*multi(s1,e1,e2)>-eps)&&
   (multi(s2,s1,e2)*multi(s2,e2,e1)>-eps);
}
point inter(point u1,point u2,point v1,point v2)
{
 point ret=u1;
 double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))
          /((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
 ret.x+=(u2.x-u1.x)*t;
 ret.y+=(u2.y-u1.y)*t;
 return ret;
}
double Area(point p1,point p2,point p3)
{
 return fabs(p1.x*p2.y-p1.y*p2.x+p2.x*p3.y-p2.y*p3.x+p3.x*p1.y-p3.y*p1.x)/2;
}
int main()
{
 int cas,i,flag1,flag2;
 double maxy1,maxy2,area;
 point t,t1,t2,t3,t4;
 scanf("%d",&cas);
 while(cas--)
 {
  for(i=0;i<4;i++)
  scanf("%lf%lf",&p[i].x,&p[i].y);
  if(!is(p[0],p[1],p[2],p[3]))
   printf("0.00\n");
  else if(fabs(p[0].y-p[1].y)<eps||fabs(p[2].y-p[3].y)<eps)
   printf("0.00\n");
  else
  {
   t=inter(p[0],p[1],p[2],p[3]);
   area=1;
   if(p[0].y-p[1].y>eps)
   {
    maxy1=p[0].y;
    flag1=0;
   }
   else
   {
    maxy1=p[1].y;
    flag1=1;
   }
   if(p[2].y-p[3].y>eps)
   {
    maxy2=p[2].y;
    flag2=2;
   }
   else
   {
    maxy2=p[3].y;
    flag2=3;
   }
   if(maxy1-maxy2<-eps)
   {
    t1=p[flag1];
    t4.x=t1.x;t4.y=10005;
    if(is(t1,t4,p[2],p[3]))
     area=0;
    else
    {
     t3.y=t1.y;t3.x=10005;
     t2=inter(t1,t3,p[2],p[3]);
    }
   }
   else
   {
    t1=p[flag2];
    t4.x=t1.x;t4.y=10005;
    if(is(t1,t4,p[0],p[1]))
     area=0;
    else
    {
     t3.y=t1.y;t3.x=10005;
     t2=inter(t1,t3,p[0],p[1]);
    }
   }
   if(area>eps)
            area=Area(t,t1,t2);
            printf("%.2lf\n",area);
  }
 }
 return 0;
}
   
   
   
  
  

  评论这张
 
阅读(258)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018