这题粗看还以为是线段与线段相交，但是题目要求，线段完全在矩形内也是算相交。所以可以变成目标线段a所在的直线与矩形的各个线段相交问题，然后再看该线段a是否在矩形范围内。
#include <iostream>
using namespace std;
struct Point
{
Point()
{
x=0.0f;
y=0.0f;
}
Point(double tx,double ty)
{
x=tx;
y=ty;
}
double x,y;
};
struct Segment
{
Point point1,point2;
};
double Min(doub...
阅读全文
问题说白了就是：看给定的点在哪两个线段之间。根据题目的描述，给定的点要么在线段左边，要么右边，所以需做一个叉积，来判定点与两条线段的位置关系（具体如下面的FindBelongBinIndex()函数描述）。
因为线段是排好序的了，所以可以二分查找。
#include <iostream>
#include <algorithm>
using namespace std;
struct Point2D
{
Point2D()
{
x=0.0f;
y=0.0f;
}
Point2D(double tx,dou...
阅读全文
两种解法，其中一种是用单调栈。
我想到的是另外一种：最大的矩形，中间一定有个最矮的某个单位矩形，所以求出每个包含矩形histogram[i]的最大矩形的面积，输出这些面积中最大那个即可。
key：用两个数组记录histogram[i]左右两边第一个比它小的单位矩形的序号leftLowerId[i]和rightLowerId[i]，那么对于histogram[i]，它自己的最大矩形面积就是(rightLowerId[i] - leftLowerId[i] - 1) * histogram[i]。
这里找leftLowerId...
阅读全文
N个任务排成一个序列在一台机器上等待完成（顺序不得改变），这N个任务被分成若干批，每批包含相邻的若干任务。 从时刻0开始，这些任务被分批加工，第i个任务单独完成所需的时间是Ti。在每批任务开始前，机器需要启动时间S，而完成这批任务所需的时间是各个任务需 要时间的总和（同一批任务将在同一时刻完成）。每个任务的费用是它的完成时刻乘以一个费用系数Fi。请确定一个分组方案，使得总费用最小。（1 <= N <= 10000...
阅读全文
Minimizing maximizer
Time Limit: 5000MS
Memory Limit: 30000K
Total Submissions: 3118
Accepted: 1224
Description
The company Chris Ltd. is preparing a new sorting hardware called Maximizer. Maximizer has n inputs numbered from 1 to n. Each input represents one integer. Maximizer has one output which represents the maximum value present on Maximizer's inputs.
Maximizer is im...
阅读全文
To the Max
Time Limit: 1000MS
Memory Limit: 10000K
Total Submissions: 38220
Accepted: 20161
Description
Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1*1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the
sub-rectangle ...
阅读全文
Coins
Time Limit: 3000MS
Memory Limit: 30000K
Total Submissions: 26605
Accepted: 9026
Description
People in Silverland use coins.They have coins of value A1,A2,A3...An Silverland dollar.One day Tony opened his money-box and found there were some coins.He decided to buy a very nice watch in a nearby shop. He wanted to pay the exact price(without change)
and he known the pri...
阅读全文
Maximum sum
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 31468
Accepted: 9665
Description
Given a set of n integers: A={a1, a2,..., an}, we define a function d(A) as below:
Your task is to calculate d(A).
Input
The input consists of T(<=30) test cases. The number of test cases (T) is given in the first line of the input.
Each test case contains two lines...
阅读全文
Cow Exhibition
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 8273
Accepted: 3047
Description
"Fat and docile, big and dumb, they look so stupid, they aren't much
fun..."
- Cows with Guns by Dana Lyons
The cows want to prove to the public that they are both smart and fun. In order to do this, Bessie has organized an exhibition that will be put on by the cows....
阅读全文
Space Elevator
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 7618
Accepted: 3591
Description
The cows are going to space! They plan to achieve orbit by building a sort of space elevator: a giant tower of blocks. They have K (1 <= K <= 400) different types of blocks with which to build the tower. Each block of type i has height h_i (1 <= h_i <= 100)
...
阅读全文