深信服校园招聘c/c 软件开发E卷

二维平面上给定一个凸多边形和若干点，小强想要查询有多少个点在凸多边形内部，在边上的点不算作内部）。
凸多边形由顺序的顶点序列构成，顶点以及要查询的点都在整数坐标上。
如由(1,0), (0,1), (-1,0), (0,-1)构成的四边形中，(0,0)点在内部，而(1,1)点在外部。
输入描述： 首先输入vn（n<=1e4），表示凸多边形的顶点个数；
接下来输入vn个顶点，每个顶点由两个整数构成，分别表示横纵坐标x、y（-1e4<=x,y<=1e4）；
然后输入pn（pn<=1e4），表示要查询数；
接下来输入pn个点，每个点由两个整数构成，分别表示横纵坐标x、y（-1e4<=x,y<=1e4）。输入样例： 4 1 0 0 1 -1 0 0 -1 2 0 0 1 1 输出描述： 输出一个整数，表示在凸多边形内部的点数输出样例 1

【题目】
空地上竖立着n个从左到右排列的木板，它们可以把水挡住，但溢出最边上木板的水将会流到空地上。
已知木板间距都是单位1，现给定每个木板的高度，请求出总共能接住的水量？
说明一点，这里只考虑间距（宽度）和高度，不考虑第三个维度，因此水量是平方单位。

示例1，木板高度分别是2,1,3，那么我们可以接住2*2=4平方单位的水，如下图所示。注意，中间那个木板被水淹没了。
    |
|- -|
|-|-|

示例2，木板高度分别是2,4,3，那么可以接住2*1+3*1=5平方单位的水，如下图所示。
  |
  |-|
|-|-|
|-|-|


输入描述： 第一行一个正整数T，表示T个测试样例；
对于每个测试样例，
输入正整数n（n<=1e5），表示n块木板；
接下来输入n个正整数，表示木板高度h（h<1e4）。输入样例： 2 3 2 1 3 3 2 4 3 输出描述： 输出T行，每行一个正整数，表示每个样例能接住的最大平方单位的水量。输出样例 4 5

有一个非常非常大的长方形蛋糕，蛋糕左下角是原点(0,0)。
兔子打算切出个长方形的小蛋糕来吃，但为了减肥它只打算切一刀，这一刀可能包含n步，每一步可以往横向或纵向走一个单位长度，总长度为n。
假设兔子切的起点是(x,0)，问能切出的最大蛋糕面积是多少？需要注意的是，要求蛋糕必须是长方形的。
示例1，在x=1、n=3时，可以切出面积为2的最大蛋糕，刀的走向是：上上左，将角落上的蛋糕切下来。
|←
|  ↑
|_↑_ _
  

示例2，在x=3、n=3时，可以切出面积为1的最大蛋糕，刀的走向是：上右下，将边上的蛋糕切下来。
|
|         →
|_ _ _↑_↓_
输入描述： 第一行一个正整数T，表示T个测试样例；
对于每个测试样例，
输入整数x（1=<x<1e4），表示起点(x,0)；
接着输入整数n（3=<n<1e4），表示切的长度n。输入样例： 2 1 3 100 3 输出描述： 输出T行，每行一个正整数，表示每个样例能切出的最大面积输出样例 2 1