LA 4992 Jungle Outpost(半平面交)

Jungle Outpost

【题目链接】Jungle Outpost

【题目类型】半平面交

&题解：

蓝书282 我自己写的代码居然AC了!!!

刘汝佳的说要right要-3什么的,还要特判3,我感觉就不需要,所以我就没写,交了一发,想着应会wa吧,结果居然tmA了!!!

&代码：

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <vector>

using namespace std;

struct Point {

	double x, y;

	Point(double x = 0, double y = 0): x(x), y(y) {}

};

typedef Point Vector;

Vector operator + (Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); }

Vector operator - (Vector A, Vector B) { return Vector(A.x - B.x, A.y - B.y); }

Vector operator * (Vector A, double p) { return Vector(A.x * p, A.y * p); }

bool operator < (Point a, Point b) { return a.x < b.x || (a.x == b.x && a.y < b.y); }

double Cross(Vector A, Vector B) { return A.x * B.y - A.y * B.x; }

double PolygonArea(vector<Point> p) {

	int n = p.size();

	double ans = 0;

	for(int i = 1; i < n - 1; i++) {

		ans += Cross(p[i] - p[0], p[i + 1] - p[0]);

	}

	return ans / 2;

}

struct Line {

	Point p, v;

	double ang;

	Line() {}

	Line(Point p, Vector v): p(p), v(v) { ang = atan2(v.y, v.x); }

	bool operator <(const Line& l) const {

		return ang < l.ang;

	}

};

const double eps = 1e-9;

bool OnLeft(Line l, Point p) {

	//bug 是p-l.p  不是l.p-p

	return Cross(l.v, p - l.p) > 0;

}

Point LineInter(Line a, Line b) {

	Vector u = a.p - b.p;

	double t = Cross(b.v, u) / Cross(a.v, b.v);

	return a.p + a.v * t;

}

vector<Point> HalfplaneIntersection(vector<Line> L) {

	int n = L.size();

	sort(L.begin(), L.end());

	int first, last;

	vector<Point> p(n), ans;

	vector<Line> que(n);

	que[first = last = 0] = L[0];

	for(int i = 1; i < n; i++) {

		while(first < last && !OnLeft(L[i], p[last - 1])) last--;

		while(first < last && !OnLeft(L[i], p[first])) first++;

		que[++last] = L[i];

		if(fabs(Cross(que[last].v, que[last - 1].v)) < eps) {

			last--;

			if(OnLeft(que[last], L[i].p)) que[last] = L[i];

		}

		if(first < last) p[last - 1] = LineInter(que[last], que[last - 1]);

	}

	while(first < last && !OnLeft(que[first], p[last - 1])) last--;

	if(last - first <= 1) return ans;

	p[last] = LineInter(que[first], que[last]);

	for(int i = first; i <= last; i++) {

		ans.push_back(p[i]);

	}

	return ans;

}

int main() {

	//("E:1.in", "r", stdin);

	int n;

	while(~scanf("%d", &n)) {

		vector<Point> p;

		int x, y;

		for(int i = 0; i < n; i++) {

			scanf("%d%d", &x, &y);

			p.push_back(Point(x, y));

		}

		reverse(p.begin(), p.end());

		int left = 0, right = n;

		while(left <= right) {

			int mid = left + right >> 1;

			vector<Line> L;

			for(int i = 0; i < n; i++) {

				L.push_back(Line(p[i], p[(i + mid + 1) % n] - p[i]));

			}

			vector<Point> pp = HalfplaneIntersection(L);

			if(pp.empty()) right = mid - 1;

			else left = mid + 1;

			// printf("%d   %d   %d \n", left, mid, right);

		}

                //这要输出了答案是left 跟right没有关系

		printf("%d\n", left);

		// printf("%d\n", right);

	}

	return 0;

}