[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

常年不在线的QQ:
49750

不定期更新的GitHub:
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