poj 2826 An Easy Problem?! (线段相交问题终极版…并不easy)

An Easy Problem?!
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 11066   Accepted: 1673

Description

It’s raining outside. Farmer Johnson’s bull Ben wants some rain to water his flowers. Ben nails two wooden boards on the wall of his barn. Shown in the pictures below, the two boards on the wall just look like two segments on the plane, as they have the same width. 

Your mission is to calculate how much rain these two boards can collect. 

Input

The first line contains the number of test cases. 
Each test case consists of 8 integers not exceeding 10,000 by absolute value, x1y1x2y2x3y3x4y4. (x1y1), (x2y2) are the endpoints of one board, and (x3y3), (x4y4) are the endpoints of the other one. 

Output

For each test case output a single line containing a real number with precision up to two decimal places – the amount of rain collected. 

Sample Input

Sample Output

接下来是,crossp正好和lowp重合,肯定无解。

 

然而如果用c*h/2的话,2,3两种情况可以不用单独考虑,因为会得出h==0,答案自然为0

 

接下来比较难想到的是,口被封住的情况。

虽然我想到了这种情况,但是判定条件想错了。

我误以为两个末端点在p3的同侧的话,口就会无解。

但如下图

这种情况却是有解的,答案不为0

这步判定想错是我WA了多次最主要的原因QAQ

不过只要稍微改动下就好

 

只有x在lowp那条线的左边且lowp在anotherline末端点的左边

或者x在lowp那条线的右边且lowp在anotherline末端点的右边  口才会被封住。 

 

 

View Code

 

 

Posted in ACM

说点什么

您将是第一位评论人!

提醒
wpDiscuz