Gym - 101808E Floods ACM ICPC, Damascus University Collegiate Programming Contest(2018)-E

本文主要是介绍Gym - 101808E Floods ACM ICPC, Damascus University Collegiate Programming Contest(2018)-E,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

传送门:http://codeforces.com/gym/101808/problem/E

E-Floods

You probably heard and even saw the heavy rains that flooded the streets of Damascus recently.

Shahhoud is wondering if he should go to university or not. He asked you to find out how much rainwater is filling his street.

To make things simple, you can imagine Shahhoud's street as a 2D polyline consisting of N points. A 2D polyline is a number of points such that every point is connected to the point before it by a line segment. It is guaranteed that any vertical line crosses the polyline in at most one point.

Rain falls from above the polyline down the y axis. Your task is to calculate the total area that keeps rainwater.

The image below describes the second sample test:

 

Input

The first line contains a single integer T, the number of test cases.

Each test case starts with a line containing one integer N (1 ≤ N ≤ 105), the number of points in the polyline that represents the street Shahhoud lives in.

The following N lines describe the points of the polyline. The ith line contains two space separated integers xi and yi, the ith point of the polyline. (0 ≤ xi, yi ≤ 106). It is guaranteed that xi < xi + 1 for every 1 ≤ i < N.

Output

For each test case, print one line containing the total area that keeps rainwater.

Your answer will be considered correct if the relative error is less than 10 - 6.

Example

Input

2
2
1 1
2 1
7
1 1
2 0
3 1
5 5
7 2
8 3
9 0

Output

0.00000000
1.83333333

题意:给n个x坐标递增的点,求如图那样可以积水的阴影面积。

思路:看左边的图,可以考虑把每个水坑分割成三角形或者是梯形。s1的计算方法看右图,假设当前你在看x2,y2这个点,你发现x1这个点比它低,但是sta那个点限制了高度,阴影面积的计算:竖着的很好算,sta的y去-y1。横着的取大的三角形x1-x2,再乘以(y-y1)/(y2-y1)。s2和s3计算方法很朴素,就是当前计算的两个点的x差值,再乘以 限制的sta的y分别减去两个点的高度再相加(梯形里就是上底加下底),最后/2.那么接下来最后的问题就是怎么求每次切割的限制高度sta了,分别统计每个点左边最高点的y和右边最高点的y,每次取较小的那个,记为sta_y。如果这个点高度比当前读的点和下一个点都高,那就可以求s3那样的三角形,或者s2那样的矩形,如果是在两个点之间,那就是s1那种相似的计算啦。

代码:

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
#include<map>
#include<vector>
#include<set>
#include<queue>
using namespace std;
const int maxv = 1e5 + 5;double ans = 0;
int t, n, x[maxv], y[maxv], l[maxv], r[maxv];int main()
{ios::sync_with_stdio(false);//经大佬提醒,G++不关同步会T,大家要养成用cin和cout关同步的好习惯哦cin >> t;while (t--){cin >> n;for (int i = 1; i <= n; i++)cin >> x[i] >> y[i];int maxx = -1;for (int i = 1; i <= n; i++){maxx = max(maxx, y[i]);l[i] = maxx;}maxx = -1;for (int i = n; i >= 1; i--){maxx = max(maxx, y[i]);r[i] = maxx;}ans = 0;for (int i = 1; i <= n - 1; i++){int down, up;if (y[i] <= y[i + 1]){down = i;up = i + 1;}else{down = i + 1;up = i;}int sta = min(l[down], r[down]);if (sta >= y[down] && sta >= y[up]){ans += (double)(x[i + 1] - x[i])*(double)(2 * sta - y[down] - y[up])*0.5;}else if (sta > y[down]){ans += (double)(x[i + 1] - x[i])*(double)(sta - y[down])*(double)(sta - y[down]) / (y[up] - y[down])*0.5;}}printf("%.8lf\n", ans);}return 0;
}

 

这篇关于Gym - 101808E Floods ACM ICPC, Damascus University Collegiate Programming Contest(2018)-E的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/687452

相关文章

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

BUUCTF靶场[web][极客大挑战 2019]Http、[HCTF 2018]admin

目录   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 [web][HCTF 2018]admin 考点:弱密码字典爆破 四种方法:   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 访问环境 老规矩,我们先查看源代码

2014 Multi-University Training Contest 8小记

1002 计算几何 最大的速度才可能拥有无限的面积。 最大的速度的点 求凸包, 凸包上的点( 注意不是端点 ) 才拥有无限的面积 注意 :  凸包上如果有重点则不满足。 另外最大的速度为0也不行的。 int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1 ;}struct poin

2014 Multi-University Training Contest 7小记

1003   数学 , 先暴力再解方程。 在b进制下是个2 , 3 位数的 大概是10000进制以上 。这部分解方程 2-10000 直接暴力 typedef long long LL ;LL n ;int ok(int b){LL m = n ;int c ;while(m){c = m % b ;if(c == 3 || c == 4 || c == 5 ||

2014 Multi-University Training Contest 6小记

1003  贪心 对于111...10....000 这样的序列,  a 为1的个数,b为0的个数,易得当 x= a / (a + b) 时 f最小。 讲串分成若干段  1..10..0   ,  1..10..0 ,  要满足x非递减 。  对于 xi > xi+1  这样的合并 即可。 const int maxn = 100008 ;struct Node{int

AtCoder Beginner Contest 370 Solution

A void solve() {int a, b;qr(a, b);if(a + b != 1) cout << "Invalid\n";else Yes(a);} B 模拟 void solve() {qr(n);int x = 1;FOR(i, n) FOR(j, i) qr(a[i][j]);FOR(i, n) x = x >= i ? a[x][i]: a[i][x];pr2(

2018秋招C/C++面试题总结

博主从8月中旬开始大大小小面试了十几家公司,至今也许是告一段落吧,希望后面会有好结果,因此总结记录一些C/C++方向常见的问题。和大家一起学习! 参考了互联网的各种资源,自己尝试归类整理,谢谢~ 一、C和C++的区别是什么? C是面向过程的语言,C++是在C语言的基础上开发的一种面向对象编程语言,应用广泛。 C中函数不能进行重载,C++函数可以重载 C++在C的基础上增添类,C是一个结构

大厂算法例题解之网易2018秋招笔试真题 (未完)

1、字符串碎片 【题目描述】一个由小写字母组成的字符串可以看成一些同一字母的最大碎片组成的。例如,“aaabbaaac” 是由下面碎片组成的:‘aaa’,‘bb’,‘c’。牛牛现在给定一个字符串,请你帮助计算这个字符串的所有碎片的 平均长度是多少。 输入描述: 输入包括一个字符串 s,字符串 s 的长度 length(1 ≤ length ≤ 50),s 只含小写字母(‘a’-‘z’) 输出描述

【转载】ACM感悟

今天看了一篇我们学校前辈的ACM的感悟,觉得写的十分有道理,这里转载,文章还会不断的改进和更新。 原文链接:http://www.cnblogs.com/Chierush/p/3760870.html?ADUIN=1339764596&ADSESSION=1401536826&ADTAG=CLIENT.QQ.5329_.0&ADPUBNO=26349 声明:本文是写给弱校ACM新手的一点

我们依旧在追梦的路上-山东省第六届ACM比赛总结

这场比赛从结果而言达到了预期(金牌),从过程而言和我的预期相差甚远(打的太乱,个人发挥很差),还好关键时刻队友抗住压力,负责后果真的不堪设想。 热身赛 热身赛纯粹测机器的,先把A,B,C草草水过(A题小写x打成大写的也是醉了),我和老高开始各种测机器,long long不出所料是lld的,试了一下除0和数组越界的re问题,发现没有re,只有wa(甚至数组越界还AC了),至于栈深的话也没过多追