csu 1812（半平面交求面积）

题目链接：

http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1812

题解：

用半平面交求出三角形和矩形的交的点集，然后用叉积就可以求出面积了，注意需要逆时针输入多边形的点

AC代码：

#include <bits/stdc++.h> using namespace std; typedef complex<double> Point; typedef pair<Point, Point> Halfplane; typedef vector<Point> Convex;//多边形 const double EPS = 1e-10; inline int sgn(double n) { return fabs(n) < EPS ? 0 : (n < 0 ? -1 : 1); } inline double det(Point a, Point b) { return (conj(a)*b).imag(); } inline double dot(Point a, Point b) { return (conj(a)*b).real(); } inline double onLeft(Point a, Halfplane p) { return sgn(det(a - p.first, p.second - p.first)) <= 0; } Point crossPoint(const Halfplane& a, const Halfplane& b) { double k = det(b.first - b.second, a.first - b.second); k = k / (k - det(b.first - b.second, a.second - b.second)); return a.first + (a.second - a.first) * k; } bool cmp(const Halfplane& a, const Halfplane& b) { int res = sgn(arg(a.second - a.first) - arg(b.second - b.first)); return res == 0 ? onLeft(a.first, b) : res < 0; } vector<Point> halfplaneIntersection(vector<Halfplane> v) { sort(v.begin(), v.end(), cmp); deque<Point> ans; deque<Halfplane> q; q.push_back(v[0]); for(int i = 1; i < int(v.size()); ++i) { if(sgn(arg(v[i].second - v[i].first) - arg(v[i-1].second - v[i-1].first)) == 0) continue; while(ans.size() > 0 && !onLeft(ans.back(), v[i])) ans.pop_back(), q.pop_back(); while(ans.size() > 0 && !onLeft(ans.front(), v[i])) ans.pop_front(), q.pop_front(); ans.push_back(crossPoint(q.back(), v[i])); q.push_back(v[i]); } while(ans.size() > 0 && !onLeft(ans.back(), q.front())) ans.pop_back(), q.pop_back(); while(ans.size() > 0 && !onLeft(ans.front(), q.back())) ans.pop_front(), q.pop_front(); ans.push_back(crossPoint(q.back(), q.front())); return vector<Point>(ans.begin(), ans.end()); } double x1,yy1,x2,y2; double x3,y3,x4,y4; int main() { while(~scanf("%lf %lf %lf %lf", &x1, &yy1, &x2, &y2)) { Convex tri,rect; tri.push_back(Point(x1,yy1)); if((x2 >= x1 && y2 >= yy1) || (x2 <= x1 && y2 <= yy1)) { tri.push_back(Point(x2,yy1)); tri.push_back(Point(x1,y2)); } else { tri.push_back(Point(x1,y2)); tri.push_back(Point(x2,yy1)); } scanf("%lf %lf %lf %lf", &x3, &y3, &x4, &y4); rect.push_back(Point(x3,y3)); if((x4 >= x3 && y4 >= y3) || (x4 <= x3 && y4 <= y3)) { rect.push_back(Point(x4,y3)); rect.push_back(Point(x4,y4)); rect.push_back(Point(x3,y4)); } else { rect.push_back(Point(x3,y4)); rect.push_back(Point(x4,y4)); rect.push_back(Point(x4,y3)); } vector <Halfplane> ans; for(int i = 0; i < tri.size(); i++)ans.push_back(Halfplane(tri[i], tri[(i+1) % tri.size()])); for(int i = 0; i < rect.size(); i++)ans.push_back(Halfplane(rect[i], rect[(i+1) % rect.size()])); vector<Point> ansans = halfplaneIntersection(ans); double ansarea = 0; for(int i = 1; i < ansans.size(); i++) { //cout << ansans[i] << " " <<ansans[i-1] <<endl; ansarea += det(ansans[i], ansans[i-1]); } //cout << ansans[0] << " " <<ansans[ansans.size()-1] <<endl; ansarea += det(ansans[0], ansans[ansans.size()-1]); printf("%.8f\n", fabs(ansarea)/2); } return 0; }