计算几何 POJ 2653 Pick-up sticks

Problem

Stan has n sticks of various length. He throws them one at a time on the floor in a random way. After finishing throwing, Stan tries to find the top sticks, that is these sticks such that there is no stick on top of them. Stan has noticed that the last thrown stick is always on top but he wants to know all the sticks that are on top. Stan sticks are very, very thin such that their thickness can be neglected.

Input

Input consists of a number of cases. The data for each case start with 1 <= n <= 100000, the number of sticks for this case. The following n lines contain four numbers each, these numbers are the planar coordinates of the endpoints of one stick. The sticks are listed in the order in which Stan has thrown them. You may assume that there are no more than 1000 top sticks. The input is ended by the case with n=0. This case should not be processed.

Output

For each input case, print one line of output listing the top sticks in the format given in the sample. The top sticks should be listed in order in which they were thrown.
The picture to the right below illustrates the first case from input.

Sample Input

5
1 1 4 2
2 3 3 1
1 -2.0 8 4
1 4 8 2
3 3 6 -2.0
3
0 0 1 1
1 0 2 1
2 0 3 1
0

Sample Output

Top sticks: 2, 4, 5.
Top sticks: 1, 2, 3.

思路

模板题。不过注意复杂度，需要高效地判断(最后放下的一定在最上面，所以直接输出即可。对于整个线段集合，（除了最后一个线段）从前往后开始判断是不是和后面（除了最后一个线段）任何一个线段有相交，只要有相交，就排除，因此他不可能是最上面的；否则，输出)，不然就会TLE。

代码

通过

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <string>
#include <math.h>
using namespace std;
struct Point {
	double x, y;
	Point() {

	}
	Point(double x2, double y2) {
		x = x2;
		y = y2;
	}
	Point operator -(const Point &b)const
	{
		return Point(x - b.x, y - b.y);
	}
	double operator ^(const Point &b)const
	{
		return x * b.y - y * b.x;
	}
};
struct Edge {
	Point up;
	Point down;
	Edge() {

	}
	Edge(Point up2, Point down2)
	{
		up = up2; down = down2;
	}
};
const int MAXN = 100000;
const double EPS = 1e-8;


double dis(Point a, Point b)
{
	return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

int sgn(double x)
{
	if (fabs(x) < EPS) return 0;  //overlap 有公共点
	if (x < 0) return -1; //在两侧
	return 1;  //在一侧
}
//判断线段相交   l1是原线段
bool inter(Edge l1, Edge l2)
{

	return sgn((l2.down - l1.down) ^ (l1.up - l1.down))*sgn((l2.up - l1.down) ^ (l1.up - l1.down)) <= 0;
	
}

// 每个线段打个标记

Edge con[MAXN];
int indexcon[MAXN];


int main(void) {
	int m;
	ios::sync_with_stdio(false);  //关闭
	while (cin >> m && m) {
		double x1, y1, x2, y2;
		for (int i = 0; i < m; i++)
		{
			scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
			con[i] = Edge(Point(x1, y1), Point(x2, y2));
		}
		printf("Top sticks: ");
		for (int i = 0; i < m - 1; i++)
		{
			int j = i + 1;
			for (j = i + 1; j < m; j++)  
			{
				if (inter(con[i], con[j])&& inter(con[j], con[i])) break;
			}
			if (j == m) printf("%d, ", i + 1);
		}
		printf("%d.\n", m);//最后一个 -> 一定在最上面
	}
	return 0;

}

第一发

一开始没想那么多，直接每次来一个都与之前的暴力判断$O(n^2)$O(n2)。结果必然是TLE。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <string>
#include <math.h>
using namespace std;
struct Point {
	double x, y;
	Point() {

	}
	Point(double x2, double y2) {
		x = x2;
		y = y2;
	}
	Point operator -(const Point &b)const
	{
		return Point(x - b.x, y - b.y);
	}
	double operator ^(const Point &b)const
	{
		return x * b.y - y * b.x;
	}
};
struct Edge {
	Point up;
	Point down;
	Edge() {

	}
	Edge(Point up2, Point down2)
	{
		up = up2; down = down2;
	}
};
const int MAXN = 100000;
const double EPS = 1e-8;


double dis(Point a, Point b)
{
	return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

int sgn(double x)
{
	if (fabs(x) < EPS) return 0;  //overlap 有公共点
	if (x < 0) return -1; //在两侧
	return 1;  //在一侧
}
//判断线段相交   l1是原线段
bool inter(Edge l1, Edge l2)
{

	return sgn((l2.down - l1.down) ^ (l1.up - l1.down))*sgn((l2.up - l1.down) ^ (l1.up - l1.down)) <= 0;
	
}

// 每个线段打个标记

Edge con[MAXN];
int indexcon[MAXN];
int main(void) {
	int m;
	ios::sync_with_stdio(false);  //关闭
	while (cin >> m && m) {
		double x1, y1, x2, y2;
		int max_index = -99;
		for (int i = 0; i < m; i++)
		{
			scanf_s("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
			con[i] = Edge(Point(x1, y1), Point(x2, y2));
			indexcon[i] = 0;
			max_index = 0;
			for (int j = 0; j < i; j++) {
				if (inter(con[i], con[j])&& inter(con[j], con[i])) { // 有相交
					if (indexcon[i] < indexcon[j]+1) {
						indexcon[i] = indexcon[j]+1;
						if (max_index < indexcon[i]) {
							max_index = indexcon[i];
						}
					}
				}
			}

		}
		cout << "Top sticks:" ;
		int temp = 0;
		for (int i = 0; i < m; i++) {
			if (max_index == indexcon[i]) {
				if (!temp) {
					cout << " " << i + 1;
					temp = 1;
				}
				else {
					cout << ", " <<i + 1;
				}
			}
		}
		cout << "." << endl;
	}
	return 0;

}