题目大意:有两块木板交叉起来接雨水,问最多能接多少。
 
分析:题目描述很简单,不过有些细节还是需要注意到,如下图几种情况:
 
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std; const int MAXN = ;
const double oo = 1e4+;
const double EPS = 1e-; int sign(double val)
{
if(val > EPS)return ;
if(fabs(val) < EPS)return ;
return -;
} struct Point
{
double x, y;
Point(double x=, double y=):x(x), y(y){}
Point operator - (const Point &tmp) const{
return Point(x-tmp.x, y-tmp.y);
}
double operator ^(const Point &tmp) const{
return x*tmp.y - y*tmp.x;
}
bool operator == (const Point &tmp) const{
return fabs(x-tmp.x) < EPS && fabs(y-tmp.y) < EPS;
}
double operator *(const Point &tmp) const{
return x*tmp.x + y*tmp.y;
}
};
struct Segment
{
Point s, e;
double a, b, c;///ax + by = c
Segment(Point s=, Point e=):s(s), e(e){
a = s.y - e.y;
b = e.x - s.x;
c = e.x*s.y - s.x*e.y;
}
bool Inter(const Segment &t)const{
int v1 = sign((s-e)^(t.s-e));
int v2 = sign((s-e)^(t.e-e)); if(!v1 && !v2)return false;///共线 if(!v1 && t.s.x >= min(s.x, e.x) && t.s.x <= max(s.x, e.x)
&& t.s.y >= min(s.y, e.y) && t.s.y <= max(s.y, e.y)
|| !v2 && t.e.x >= min(s.x, e.x) && t.e.x <= max(s.x, e.x)
&& t.e.y >= min(s.y, e.y) && t.e.y <= max(s.y, e.y)
|| v1 * v2 == -)return true; return false;
}
Point CrossNode(const Segment &t) const{
Point ans;
ans.x = (c*t.b-t.c*b)/(a*t.b-t.a*b);
ans.y = (c*t.a-t.c*a)/(b*t.a-t.b*a); return ans;
}
};
double Dist(Point a, Point b)
{
return sqrt((a-b) * (a-b));
}
double Find(Point crs, Point p[], int N)
{
double sum = ; for(int i=; i<N; i++)
for(int j=i+; j<N; j++)
{
int k = sign((p[i]-crs)^(p[j]-crs)); if(p[i] == p[j])continue; if(crs.x>=min(p[i].x, p[j].x) && crs.x<=max(p[i].x, p[j].x)
|| crs.x>=p[i].x && crs.x>=p[j].x && (k>&&(p[i].x-p[j].x>EPS) || k<&&(p[j].x-p[i].x>EPS))
|| crs.x<=p[i].x && crs.x<=p[j].x && (k<&&(p[j].x-p[i].x>EPS) || k>&&(p[i].x-p[j].x>EPS)))
if(p[i].y-crs.y > EPS && p[j].y-crs.y > EPS)
{
Point A = p[i].y < p[j].y ? p[i] : p[j];
Point B = (A == p[i] ? p[j] : p[i]);
Segment t1(Point(-oo, A.y), Point(oo, A.y));
Segment t2(crs, B); B = t1.CrossNode(t2); double La = Dist(A, B);
double Lb = Dist(A, crs);
double Lc = Dist(B, crs);
double p = (La+Lb+Lc) / ; sum += sqrt(p*(p-La)*(p-Lb)*(p-Lc));
}
} return sum;
} int main()
{
int T; scanf("%d", &T); while(T--)
{
Point p[MAXN], crs; scanf("%lf%lf%lf%lf", &p[].x, &p[].y, &p[].x, &p[].y);
scanf("%lf%lf%lf%lf", &p[].x, &p[].y, &p[].x, &p[].y);
Segment L1(p[], p[]), L2(p[], p[]); double ans = ; if(L1.Inter(L2) && L2.Inter(L1))
{
crs = L1.CrossNode(L2);
ans = Find(crs, p, );
} printf("%.2f\n", ans+EPS);
} return ;
}

An Easy Problem?! - POJ 2826(求面积)的更多相关文章

  1. POJ 1152 An Easy Problem! (取模运算性质)

    题目链接:POJ 1152 An Easy Problem! 题意:求一个N进制的数R.保证R能被(N-1)整除时最小的N. 第一反应是暴力.N的大小0到62.发现当中将N进制话成10进制时,数据会溢 ...

  2. hdu2601 An easy problem(数学)

    题目意思: http://acm.hdu.edu.cn/showproblem.php? pid=2601 给出一个数N,求N=i*j+i+j一共同拥有多少种方案. 题目分析: 此题直接暴力模拟就可以 ...

  3. POJ 2826 An Easy Problem?![线段]

    An Easy Problem?! Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 12970   Accepted: 199 ...

  4. POJ 2826 An Easy Problem?!

    An Easy Problem?! Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 7837   Accepted: 1145 ...

  5. POJ 2826 An Easy Problem?! --计算几何,叉积

    题意: 在墙上钉两块木板,问能装多少水.即两条线段所夹的中间开口向上的面积(到短板的水平线截止) 解法: 如图: 先看是否相交,不相交肯定不行,然后就要求出P与A,B / C,D中谁形成的向量是指向上 ...

  6. POJ 2826 An Easy Problem?! 好的标题

    受该两块木板以形成槽的效果.Q槽可容纳雨水多,注意雨爆跌,思想是非常easy,分类讨论是有点差. 1.假定两条线段不相交或平行,然后再装0: 2.有一个平行x轴.连衣裙0. 3.若上面覆盖以下的,装0 ...

  7. 【解题报告】PKU 2826 An Easy Problem?!

    原题链接:http://poj.org/problem?id=2826 一题很蛋疼的一题.目前为止还有一个问题我没搞清楚,问题注在代码中. 题目大意: 外面下雨了,农民Johnoson的bull(?? ...

  8. poj 3348--Cows(凸包求面积)

    链接:http://poj.org/problem?id=3348 Cows Time Limit: 2000MS   Memory Limit: 65536K Total Submissions:  ...

  9. [POJ] 2453 An Easy Problem [位运算]

    An Easy Problem   Description As we known, data stored in the computers is in binary form. The probl ...

随机推荐

  1. 如何给wordpress外部链接自动添加nofollow

    wordpress多作者博客可以丰富网站的内容,但同时也会产生一些无关的链接,例如有些投机的人会考虑在文章中随意添加外部链接,如果你不想给这些外部链接传递权重,你需要给这些外部链接加上 rel=&qu ...

  2. ios企业应用发布流程

    转载自:http://blog.csdn.net/justinjing0612/article/details/8758692留作备忘 企业发布app的 过程比app store 发布的简单多了,没那 ...

  3. poj 1833

    http://poj.org/problem?id=1833 next_permutation这个函数是用来全排列的,按字典的序进行排列,当排列无后继的最大值时,会执行字典升序排列,相当于排序: 当排 ...

  4. POJ1838

    poj 1838 这道题主要是对并查集的考察,在这道题的解题过程中主要用到的算法就是并查集中的最基本的makeSet,findSet,unionSet 即前篇文章中所提到的: makeSet(Elem ...

  5. iOS日期问题

    由于项目需要,需要获取去设备的当前时间,组成一个字符串,比如 2018年9月15日 15点30分30秒,需要转换成字符创:180915153030. 很简单的一个需求,于是就使用了日期格式话当前时间: ...

  6. ACM-ICPC 2018 南京赛区网络预赛 J.sum

    A square-free integer is an integer which is indivisible by any square number except 11. For example ...

  7. Java中对象和json互相转换的工具类

    package com.Dingyu.util; import java.util.List; import com.fasterxml.jackson.core.JsonProcessingExce ...

  8. MVC与单元测试实践之健身网站(七)-添加计划

    ​计划的制定涉及到周期-动作包-动作的关联操作,在上一篇<计划的添加与重置>完成了周期的设置.动作包的添加,现在要完成的是动作的添加操作. 一 具体功能 a) 在选定了一个大周期具有的天数 ...

  9. python-面向对象-02_类和对象

    类和对象 目标 类和对象的概念 类和对象的关系 类的设计 01. 类和对象的概念 类 和 对象 是 面向对象编程的 两个 核心概念 1.1 类 类 是对一群具有 相同 特征 或者 行为 的事物的一个统 ...

  10. C\C++程序结束另外的进程

    WinExec("taskkill /f /im center_flextrbo.exe",SW_HIDE);