程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA 11106 - Rectilinear Polygon（幾何+貪心）

UVA 11106 - Rectilinear Polygon（幾何+貪心）

編輯：C++入門知識

Problem B: Rectilinear polygon

Given is n points with integer coordinates in the plane. Is it is pZ喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vc3NpYmxlIHRvIGNvbnN0cnVjdCBhIHNpbXBsZSwgdGhhdCBpcyBub24taW50ZXJzZWN0aW5nLCByZWN0aWxpbmVhciBwb2x5Z29uIHdpdGggdGhlIGdpdmVuIHBvaW50cyBhcyB2ZXJ0aWNlcz8gSW4gYSByZWN0aWxpbmVhciBwb2x5Z29uIHRoZXJlIGFyZSBhdCBsZWFzdCA0IHZlcnRpY2VzIGFuZCBldmVyeSBlZGdlIGlzIGVpdGhlciBob3Jpem9udGFsIG9yIHZlcnRpY2FsOwogZWFjaCB2ZXJ0ZXggaXMgYW4gZW5kcG9pbnQgb2YgZXhhY3RseSBvbmUgaG9yaXpvbnRhbCBlZGdlIGFuZCBvbmUgdmVydGljYWwgZWRnZS4gVGhlcmUgYXJlIG5vIGhvbGVzIGluIGEgcG9seWdvbi4KPHA+PC9wPgo8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBpcyBhbiBpbnRlZ2VyIGdpdmluZyB0aGUgbnVtYmVyIG9mIGNhc2VzIHRoYXQgZm9sbG93LiBUaGUgaW5wdXQgb2YgZWFjaCBjYXNlIHN0YXJ0cyB3aXRoIGFuIGludGVnZXIgNCCh3CBuodwgMTAwMDAwIGdpdmluZyB0aGUgbnVtYmVyIG9mIHBvaW50cyBmb3IgdGhpcyB0ZXN0IGNhc2UuIEl0IGlzIGZvbGxvd2VkIGJ5IG4gcGFpcnMKIG9mIGludGVnZXJzIHNwZWNpZnlpbmcgdGhlIHggYW5kIHljb29yZGluYXRlcyBvZiB0aGUgcG9pbnRzIGZvciB0aGlzIGNhc2UuPC9wPgo8cD5UaGUgb3V0cHV0IHNob3VsZCBjb250YWluIG9uZSBsaW5lIGZvciBlYWNoIGNhc2Ugb24gaW5wdXQuIEVhY2ggbGluZSBzaG91bGQgY29udGFpbiBvbmUgaW50ZWdlciBudW1iZXIgZ2l2aW5nIHRoZSBsZW5ndGggb2YgdGhlIHJlY3RpbGluZWFyIHBvbHlnb24gcGFzc2luZyB0aHJvdWdodCB0aGUgZ2l2ZW4gcG9pbnRzIHdoZW4gaXQgZXhpc3RzOyBvdGhlcndpc2UsIGl0CiBzaG91bGQgY29udGFpbiA8dHQ+LTE8L3R0Pi48L3A+CjxoMz5TYW1wbGUgaW5wdXQ8L2gzPgo8cHJlIGNsYXNzPQ=="brush:java;">1 8 1 2 1 0 2 1 2 2 3 2 3 1 4 0 4 2

Output for sample input

題意：給定n個點，判斷這n點能不能組成一個多邊形，並且點都在直角上，如果可以輸出周長，不行輸出-1.

思路：對於橫坐標為x的所有點，如果是奇數個點，那麼肯定不行，因為同一橫坐標x的點，要能折出去再折回來，必然為偶數個，按x優先，y第二優先排序後，組成的邊必然為，0,1組，2,3組，3,4組...對於縱坐標也是同理，這樣就能求出周長了。然後在去判斷有沒有自交，判斷方式為，先把所有以x求出來的線段保存下來，然後在求y的時候，去判斷有沒有相交的邊（這步用了map，不過跑起來時間還是很短）。最後還要判斷組合出來的多邊形是否只有一個。判斷方式是，之前求線段的時候，把每個點水平和垂直連的點都求出來，隨便選一點進行dfs，判斷最後形成環的時候，點的個數等不等於n。

代碼：

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int N = 100005;
typedef pair pi;
map vis;
int t, n, en, vi[N], num;
struct Point {
	int x, y, id, v, h;
} p[N];

struct Edge {
	int x, y1, y2;
} e[N];

bool cmp1(Point a, Point b) {
	if (a.x != b.x)
		return a.x < b.x;
	return a.y < b.y;
}

bool cmp2(Point a, Point b) {
	if (a.y != b.y)
		return a.y < b.y;
	return a.x < b.x;
}

bool cmp3(Point a, Point b) {
	return a.id < b.id;
}

void init() {
	en = 0; vis.clear();
	memset(vi, 0, sizeof(vi));
	num = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &p[i].x, &p[i].y);
		p[i].id = i;
	}
}

void dfs(int id, int bo) {
	if (vi[id]) return;
	vi[id] = 1; num++;
	if (bo) dfs(p[id].v, 0);
	else dfs(p[id].h, 1);
}

int solve() {
	if (n % 2) return -1;
	int ans = 0;
	sort(p, p + n, cmp1); int i, save = -1;
	for (i = 0; i < n; i += 2) {
		if (p[i].x != p[i + 1].x) return -1;
		if (save != p[i].x) {
			vis[p[i].x].first = en;
			if (i != 0) vis[p[i - 1].x].second = en;
			save = p[i].x;
		}
		e[en].x = p[i].x; e[en].y1 = p[i + 1].y; e[en++].y2 = p[i].y;
		p[i].h = p[i + 1].id;
		p[i + 1].h = p[i].id;
		ans += (p[i + 1].y - p[i].y);
	}
	vis[p[n - 1].x].second = en;
	sort(p, p + n, cmp2);
	for (i = 0; i < n; i += 2) {
		if (p[i].y != p[i + 1].y) return -1;
		for (int j = vis[p[i].x].second; j < vis[p[i + 1].x].first; j++) {
			if (e[j].y1 >= p[i].y && e[j].y2 <= p[i].y) return -1;
		}
		p[i].v = p[i + 1].id;
		p[i + 1].v = p[i].id;
		ans += (p[i + 1].x - p[i].x);
	}
	sort(p, p + n, cmp3);
	dfs(0, 0);
	if (num != n) return -1;
	return ans;
}

int main() {
	scanf("%d", &t);
	while (t--) {
		init();
		printf("%d\n", solve());
	}
	return 0;
}