poj 2451 Uyuw's Concert (半平面交)

2451 -- Uyuw's Concert

  继续半平面交,这还是简单的半平面交求面积,不过输入用cin超时了一次。

代码如下:

 #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath> using namespace std; struct Point {
double x, y;
Point() {}
Point(double x, double y) : x(x), y(y) {}
} ;
template<class T> T sqr(T x) { return x * x;}
typedef Point Vec;
Vec operator + (Vec a, Vec b) { return Vec(a.x + b.x, a.y + b.y);}
Vec operator - (Vec a, Vec b) { return Vec(a.x - b.x, a.y - b.y);}
Vec operator * (Vec a, double p) { return Vec(a.x * p, a.y * p);}
Vec operator / (Vec a, double p) { return Vec(a.x / p, a.y / p);} const double EPS = 1e-;
const double PI = acos(-1.0);
inline int sgn(double x) { return (x > EPS) - (x < -EPS);} inline double dotDet(Vec a, Vec b) { return a.x * b.x + a.y * b.y;}
inline double crossDet(Vec a, Vec b) { return a.x * b.y - a.y * b.x;}
inline double dotDet(Point o, Point a, Point b) { return dotDet(a - o, b - o);}
inline double crossDet(Point o, Point a, Point b) { return crossDet(a - o, b - o);}
inline double vecLen(Vec x) { return sqrt(dotDet(x, x));}
inline double toRad(double deg) { return deg / 180.0 * PI;}
inline double angle(Vec v) { return atan2(v.y, v.x);}
inline Vec vecUnit(Vec x) { return x / vecLen(x);}
inline Vec normal(Vec x) { return Vec(-x.y, x.x) / vecLen(x);} const int N = ;
struct DLine {
Point p;
Vec v;
double ang;
DLine() {}
DLine(Point p, Vec v) : p(p), v(v) { ang = atan2(v.y, v.x);}
bool operator < (DLine L) const { return ang < L.ang;}
} dl[N]; inline bool onLeft(DLine L, Point p) { return crossDet(L.v, p - L.p) > ;}
Point dLineIntersect(DLine a, DLine b) {
Vec u = a.p - b.p;
double t = crossDet(b.v, u) / crossDet(a.v, b.v);
return a.p + a.v * t;
} struct Poly {
vector<Point> pt;
Poly() { pt.clear();}
~Poly() {}
Poly(vector<Point> &pt) : pt(pt) {}
Point operator [] (int x) { return pt[x];}
int size() { return pt.size();}
double area() {
double ret = 0.0;
int sz = pt.size();
pt.push_back(pt[]);
for (int i = ; i <= sz; i++) ret += crossDet(pt[i], pt[i - ]);
pt.pop_back();
return fabs(ret / 2.0);
}
} ; Poly halfPlane(DLine *L, int n) {
Poly ret = Poly();
sort(L, L + n);
int fi, la;
Point *p = new Point[n];
DLine *q = new DLine[n];
q[fi = la = ] = L[];
for (int i = ; i < n; i++) {
while (fi < la && !onLeft(L[i], p[la - ])) la--;
while (fi < la && !onLeft(L[i], p[fi])) fi++;
q[++la] = L[i];
if (sgn(crossDet(q[la].v, q[la - ].v)) == ) {
la--;
if (onLeft(q[la], L[i].p)) q[la] = L[i];
}
if (fi < la) p[la - ] = dLineIntersect(q[la - ], q[la]);
}
while (fi < la && !onLeft(q[fi], p[la - ])) la--;
if (la < fi) return ret;
p[la] = dLineIntersect(q[la], q[fi]);
for (int i = fi; i <= la; i++) ret.pt.push_back(p[i]);
return ret;
} const int dir[][] = { {, }, {, }, {, }, {, }}; int main() {
int T, n;
while (~scanf("%d", &n)) {
Point x[];
for (int i = ; i < n; i++) {
for (int j = ; j < ; j++) {
scanf("%lf%lf", &x[j].x, &x[j].y);
}
dl[i] = DLine(x[], x[] - x[]);
}
for (int i = ; i < ; i++) {
dl[n + i] = DLine(Point(10000.0 * dir[i][], 10000.0 * dir[i][]),
Point(10000.0 * dir[(i + ) & ][], 10000.0 * dir[(i + ) & ][]) - Point(10000.0 * dir[i][], 10000.0 * dir[i][]));
}
Poly tmp = halfPlane(dl, n + );
printf("%.1f\n", tmp.area());
}
return ;
}

——written by Lyon

上一篇:nodejs 之=> 函数


下一篇:TortoiseGit用户手册