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

• 2017-12-16
• 0
• 0

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

Output

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

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;
}