# [POJ 2826] An Easy Problem?! 【计算几何】

• 2017-12-16
• 0
• 0

## Problem:

 Time Limit: 1000MS Memory limit: 65536K

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

```2
0 1 1 0
1 0 2 1

0 1 2 1
1 0 1 2
```

Sample Output

```1.00
0.00
```

Source

POJ Monthly--2006.04.28, Dagger@PKU_RPWT

## Solution:

case #1: 线段不相交，答案为 0.00；

case #2: 其中有一条线段水平放置，答案为 0.00；

case #3: 两条线段斜率正负性相同，且较高线段将开口完全覆盖，答案为 0.00；

case #4: 普通情况，答案为 | vec1 × vec2 / 2 |。

## Code: O(T) [184K, 32MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define eps 1e-10
#define dmax 1e10
#define errorpoint Point(dmax, dmax)
using namespace std;

int T;

inline int dsgn(double dval){
if(fabs(dval) < eps) return 0;
return (dval < 0) ? -1 : 1;
}

#define Vector Point
struct Point{
double x, y;

Point() {}
Point(double x, double y): x(x), y(y) {}

inline Vector operator - (const Point p2) const {return Vector(x - p2.x, y - p2.y);}

inline bool operator == (const Point p2) const {return dsgn(x - p2.x) == 0 && dsgn(y - p2.y) == 0;}
};

inline double Cross(const Vector vec1, const Vector vec2) {return vec1.x * vec2.y - vec1.y * vec2.x;}

struct Segment{
Point u, v;

Segment() {}
Segment(Point u, Point v): u(u), v(v) {}
} s1, s2;

/*
inline bool is_Intersected(Segment s1, Segment s2){
if(max(s1.u.x, s1.v.x) >= min(s2.u.x, s2.v.x)
&& min(s1.u.x, s1.v.x) <= max(s2.u.x, s2.v.x)
&& max(s1.u.y, s1.v.y) >= min(s2.u.y, s2.v.y)
&& min(s1.u.y, s1.v.y) <= max(s2.u.y, s2.v.y)
&& dsgn(Cross(s1.v - s1.u, s2.u - s1.u)) * dsgn(Cross(s2.v - s1.u, s1.v - s1.u)) >= 0
&& dsgn(Cross(s2.v - s2.u, s1.u - s2.u)) * dsgn(Cross(s1.v - s2.u, s2.v - s2.u)) >= 0) return 1;
return 0;
}
*/

inline bool Point_on_Segment(Point p1, Segment s1){
if(dsgn(Cross(p1 - s1.u, s1.v - s1.u)) == 0  // p1 is on the line formed by s1
&& p1.x >= min(s1.u.x, s1.v.x) && p1.x <= max(s1.u.x, s1.v.x)
&& p1.y >= min(s1.u.y, s1.v.y) && p1.y <= max(s1.u.y, s1.v.y)) return 1;  // p1 is in the rectangle formed by s1
return 0;
}

inline Point Segment_Intersection(Segment s1, Segment s2){
double A1 = s1.u.y - s1.v.y, B1 = s1.v.x - s1.u.x, C1 = s1.u.x * s1.v.y - s1.v.x * s1.u.y;
double A2 = s2.u.y - s2.v.y, B2 = s2.v.x - s2.u.x, C2 = s2.u.x * s2.v.y - s2.v.x * s2.u.y;
double delta = A1 * B2 - A2 * B1;
if(dsgn(delta) == 0) return errorpoint;  // Two lines are parallel
Point inter((B1 * C2 - B2 * C1) / delta, (A2 * C1 - A1 * C2) / delta);  // Get the intersection of two lines
if(Point_on_Segment(inter, s1) && Point_on_Segment(inter, s2)) return inter;
return errorpoint;  // The intersection is not on the two segments
}

inline double Slope(Segment s1){
if(dsgn(s1.v.x - s1.u.x) == 0) return dmax;
return (s1.v.y - s1.u.y) / (s1.v.x - s1.u.x);
}  // Get the slope of s1

inline double Calc_x(Segment s1, double y){
double A1 = s1.u.y - s1.v.y, B1 = s1.v.x - s1.u.x, C1 = s1.u.x * s1.v.y - s1.v.x * s1.u.y;
return -(B1 * y + C1) / A1;
}  // Give y to calculate x of the point (x, y) which is on s1, make sure the slope of s1 is not zero

int main(){
scanf("%d", &T);
while(T--){
scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &s1.u.x, &s1.u.y, &s1.v.x, &s1.v.y, &s2.u.x, &s2.u.y, &s2.v.x, &s2.v.y);
Point inter = Segment_Intersection(s1, s2);
if(inter == errorpoint){
puts("0.00");
continue;
}  // Two lines have no intersection
double slp1 = Slope(s1), slp2 = Slope(s2);
if(dsgn(slp1) == 0 || dsgn(slp2) == 0){
puts("0.00");
continue;
}  // One line is horizontal
if(dsgn(slp1) > 0 && dsgn(slp2) > 0){
Segment *highSeg = (slp1 > slp2) ? &s1 : &s2, *lowSeg = (slp1 > slp2) ? &s2 : &s1;
if(max(highSeg->u.x, highSeg->v.x) >= max(lowSeg->u.x, lowSeg->v.x)){
puts("0.00");
continue;
}
}
if(dsgn(slp1) < 0 && dsgn(slp2) < 0){
Segment *highSeg = (slp1 < slp2) ? &s1 : &s2, *lowSeg = (slp1 < slp2) ? &s2 : &s1;
if(min(highSeg->u.x, highSeg->v.x) <= min(lowSeg->u.x, lowSeg->v.x)){
puts("0.00");
continue;
}
}  // The opening does not point upwards
Point s1top = (s1.u.y >= s1.v.y) ? s1.u : s1.v, s2top = (s2.u.y >= s2.v.y) ? s2.u : s2.v;
Point contop = (s1top.y <= s2top.y) ? s1top : s2top;  // Get the top water-level of the container
Segment othseg = (s1top.y <= s2top.y) ? s2 : s1;
Point othtop(Calc_x(othseg, contop.y), contop.y);  // Get the equal-height point on the other segment
double vol = fabs(Cross(contop - inter, othtop - inter) / 2);
printf("%.2f\n", vol);
}
return 0;
}
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai