JOJ 2785 赛车（半平面交）

Jilin University Online Judge System--2785:赛车
　　吉林大学OJ上的题目。中文题。
　　这是经典的半平面交的模型。直接套用半平面交的模板，不过要注意，对有向直线排序的时候要用叉积来比较，不然精度会丢失，从而导致排序出错。
代码如下：
  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <algorithm>
  5 #include <cmath>
  6 
  7 using namespace std;
  8 
  9 const double PI = acos(-1.0);
 10 const double EPS = 1e-10;
 11 inline int sgn(double x) { return (EPS < x) - (x < -EPS);}
 12 struct Point {
 13     double x, y;
 14     Point() {}
 15     Point(double x, double y) : x(x), y(y) {}
 16     bool operator < (Point a) const { return sgn(x - a.x) < 0 || sgn(x - a.x) == 0 && sgn(y - a.y) < 0;}
 17     bool operator == (Point a) const { return sgn(x - a.x) == 0 && sgn(y - a.y) == 0;}
 18 } ;
 19 typedef Point Vec;
 20 Vec operator + (Vec a, Vec b) { return Vec(a.x + b.x, a.y + b.y);}
 21 Vec operator - (Vec a, Vec b) { return Vec(a.x - b.x, a.y - b.y);}
 22 Vec operator * (Vec a, double p) { return Vec(a.x * p, a.y * p);}
 23 Vec operator / (Vec a, double p) { return Vec(a.x / p, a.y / p);}
 24 inline double dotDet(Vec a, Vec b) { return a.x * b.x + a.y * b.y;}
 25 inline double crossDet(Vec a, Vec b) { return a.x * b.y - a.y * b.x;}
 26 inline double crossDet(Point o, Point a, Point b) { return crossDet(a - o, b - o);}
 27 inline double vecLen(Vec x) { return sqrt(dotDet(x, x));}
 28 inline double ptDis(Point a, Point b) { return vecLen(a - b);}
 29 inline Vec normal(Vec x) {
 30     double len = vecLen(x);
 31     return Vec(-x.y / len, x.x / len);
 32 }
 33 inline Vec vecUnit(Vec x) { return x / vecLen(x);}
 34 
 35 struct DLine {
 36     Point p;
 37     Vec v;
 38     int id;
 39     double ang;
 40     DLine() {}
 41     DLine(Point p, Vec v) : p(p), v(v) { ang = atan2(v.y, v.x);}
 42     bool operator < (const DLine &L) const { return sgn(ang - L.ang) < 0 || sgn(ang - L.ang) == 0 && p < L.p;}
 43     bool operator == (const DLine &L) const { return p == L.p && v == L.v;}
 44 } ;
 45 
 46 inline bool onLeft(DLine L, Point p) { return sgn(crossDet(L.v, p - L.p)) >= 0;}
 47 Point dLineIntersect(DLine a, DLine b) {
 48     Vec u = a.p - b.p;
 49     double t = crossDet(b.v, u) / crossDet(a.v, b.v);
 50     return a.p + a.v * t;
 51 }
 52 
 53 const int N = 11111;
 54 Point p[N];
 55 DLine q[N], rec[N];
 56 int ans[N], ansEnd;
 57 
 58 bool cmp(DLine a, DLine b) {
 59     return crossDet(a.v, b.v) > 0.0;
 60 }
 61 
 62 void halfPlane(DLine *L, int n) {
 63     ansEnd = 0;
 64     sort(L, L + n, cmp);
 65 //    for (int i = 0; i < n; i++) cout << L[i].id << ' '; cout << endl;
 66     int fi, la;
 67     q[fi = la = 0] = L[0];
 68     for (int i = 1; i < n; i++) {
 69 //        cout << fi << "=1=" << la << endl;
 70 //        cout << L[i].v.x << ' ' << L[i].v.y << endl;
 71 //        cout << (L[i].p - p[la - 1]).x << ' ' << (L[i].p - p[la - 1]).y << endl;
 72         while (fi < la && !onLeft(L[i], p[la - 1]) && sgn(crossDet(L[i].v, L[i].p - p[la - 1]))) la--;
 73         while (fi < la && !onLeft(L[i], p[fi]) && sgn(crossDet(L[i].p, L[i].p + L[i].v, p[fi]))) fi++;
 74 //        cout << fi << "=2=" << la << endl;
 75         q[++la] = L[i];
 76         if (fabs(crossDet(q[la].v, q[la - 1].v)) < EPS) {
 77             la--;
 78             if (q[la] == L[i]) q[++la] = L[i];
 79             else if (onLeft(q[la], L[i].p)) q[la] = L[i];
 80         }
 81         if (fi < la) p[la - 1] = dLineIntersect(q[la - 1], q[la]);
 82 //        cout << p[la - 1].x << ' ' << p[la - 1].y << endl;
 83 //        cout << fi << "=3=" << la << endl;
 84     }
 85     while (fi < la && !onLeft(q[fi], p[la - 1])) la--;
 86 //    cout << fi << ' ' << la << endl;
 87     for (int i = fi; i <= la; i++) ans[ansEnd++] = q[i].id;
 88 }
 89 
 90 double B[N], A;
 91 
 92 int main() {
 93 //    freopen("in", "r", stdin);
 94     int n;
 95     while (cin >> n) {
 96         for (int i = 0; i < n; i++) scanf("%lf", &B[i]);
 97         for (int i = 0; i < n; i++) {
 98             scanf("%lf", &A);
 99             rec[i] = DLine(Point(0.0, B[i]), Vec(1.0, A));
100             rec[i].id = i + 1;
101         }
102         rec[n] = DLine(Point(0, 1), Vec(0.0, -1.0));
103         rec[n].id = 0;
104         halfPlane(rec, n + 1);
105         cout << ansEnd - 1 << endl;
106         sort(ans, ans + ansEnd);
107         for (int i = 1; i < ansEnd; i++) {
108             if (i > 1) putchar(' ');
109             printf("%d", ans[i]);
110         }
111         puts("");
112     }
113     return 0;
114 }
View Code
——written by Lyon
JOJ 2785 赛车 （半平面交）

JOJ 2785 赛车（半平面交）
