POJ 1696 Space Ant 計算幾何 叉積的應用

POJ 1696 Space Ant 計算幾何 叉積的應用

題目大意：平面內有一些點，我們要通過一些方式來走遍這所有的點，要求一個點只能走一次，只能向左轉而不能向右轉。求遍歷這些點的順序。

思路：數據范圍是可以怎麼搞都0ms的（n<=50,case<=100），所以只要有思路就可以了。

只能左轉，想想好像有點像凸包啊。但是這個題要遍歷所有的點，所以就把已經走過的點刪掉，然後像凸包一樣的往前走，每次找一個沒走過的極角最小的點走，然後把它標記上。最後都走完就全部遍歷完了。

CODE：

#include 
#include 
#include 
#include 
#include 
#define MAX 110
#define INF 0x7f7f7f7f
using namespace std;

struct Point{
	int _id;
	double x,y;
	double alpha;

	Point(double _x,double _y):x(_x),y(_y) {}
	Point() {}
	Point operator -(const Point &a) {
		return Point(x - a.x,y - a.y);
	}
	bool operator <(const Point &a)const {
		return alpha < a.alpha;
	}
	void Read() {
		scanf("%d%lf%lf",&_id,&x,&y);
	}
	bool Cross(Point &a,Point &b) {
		Point p1 = *this - a,p2 = *this - b;
		return p1.x * p2.y - p2.x * p1.y < 0;
	}
}point[MAX],now;

int cases,points;

int rubbish;

inline void Initialize();

int main()
{
	for(cin >> cases;cases; --cases) {
		scanf("%d",&points);
		Initialize();
		for(int x,y,i = 1;i <= points; ++i) { 
			point[i].Read();
			if(point[i].y < now.y)
				now = point[i];
		}
		printf("%d",points);
		now.x = 0;
		point[0] = now;
		for(int i = 1;i <= points; ++i) {
			for(int j = i + 1;j <= points; ++j)
				if(point[j].Judge(point[i],point[i - 1]))
					swap(point[i],point[j]);
			printf(" %d",point[i]._id);
		}
		puts("");
	}
	return 0;
}

inline void Initialize()
{
	now = Point(0,INF);
}