UVALive

UVALive - 3263 That Nice Euler Circuit （几何）

ACM

题目地址：
UVALive - 3263 That Nice Euler Circuit

题意：
给出一个点，问连起来后的图形把平面分为几个区域。

分析：
欧拉定理有：设平面图的顶点数、边数、面数分别V,E,F则V+F-E=2
大白的题目，做起来还是非常有技巧的。

代码：

/*
*  Author:      illuz <iilluzen[at]gmail.com>
*  File:        LA3263.cpp
*  Create Date: 2014-09-18 23:18:47
*  Descripton:  V+F-E=2
*/

#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;
#define repf(i,a,b) for(int i=(a);i<=(b);i++)

typedef long long ll;

const int N = 310;
const double eps = 1e-8;
const double PI = acos(-1.0);

int sgn(double x) {
	if (fabs(x) < eps) return 0;
	if (x < 0) return -1;
	else return 1;
}

struct Point {
	double x, y;
	Point() {}
	Point(double _x, double _y) {
		x = _x; y = _y;
	}
	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;
	}

	//点积
	double operator *(const Point &b) const {
		return x*b.x + y*b.y;
	}
	//绕原点旋转角度B(弧度值),后x,y的变化
	void transXY(double B) {
		double tx = x,ty = y;
		x = tx*cos(B) - ty*sin(B);
		y = tx*sin(B) + ty*cos(B);
	}

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

	bool operator ==(const Point &b) const {
		return x == b.x && y == b.y;
	}

	void read() {
		scanf("%lf", &x);
		scanf("%lf", &y);
	}

	void print() {
		printf("debug: x = %f, y = %f
", x, y);
	}
};

struct Line
{
	Point s,e;
	Line(){}
	Line(Point _s,Point _e) {
		s = _s;e = _e;
	}

	//两直线相交求交点
	//第一个值为0表示直线重合,为1表示平行,为0表示相交,为2是相交
	//仅仅有第一个值为2时,交点才有意义
	pair<int,Point> operator &(const Line &b)const {
		Point res = s;
		if(sgn((s-e)^(b.s-b.e)) == 0) {
			if(sgn((s-b.e)^(b.s-b.e)) == 0)
				return make_pair(0,res);//重合
			else return make_pair(1,res);//平行
		}
		double t = ((s-b.s)^(b.s-b.e)) / ((s-e)^(b.s-b.e));
		res.x += (e.x-s.x)*t;
		res.y += (e.y-s.y)*t;
		return make_pair(2,res);
	}
};

//*两点间距离
double dist(Point a,Point b) {
	return sqrt((a-b)*(a-b));
}

//*推断点在线段上
bool OnSeg(Point P,Line L) {
	return
		sgn((L.s-P)^(L.e-P)) == 0 &&
		sgn((P.x - L.s.x) * (P.x - L.e.x)) <= 0 &&
		sgn((P.y - L.s.y) * (P.y - L.e.y)) <= 0;
}

Point p[N], v[N*N];
Line a, b;
int c, e, n, cas;

int main() {
	ios_base::sync_with_stdio(0);
	cas = 0;
	while (scanf("%d", &n) && n) {
		repf (i, 0, n - 1) {
			p[i].read();
			v[i] = p[i];
		}
		n--;
		c = n;
		repf (i, 0, n - 1) {
			a.s = p[i];
			a.e = p[i + 1];
			repf (j, i + 1, n - 1) {
				b.s = p[j];
				b.e = p[j + 1];
				pair<int,Point> t = a & b;
				if (t.first == 2 && OnSeg(t.second, a) && OnSeg(t.second, b))
					v[c++] = t.second;
			}
		}
		sort(v, v + c);
		c = unique(v, v + c) - v;
		
		e = n;
		repf (j, 0, n - 1) {
			a.s = p[j];
			a.e = p[j + 1];
			repf (i, 0, c - 1) {
				if (p[j] == v[i] || p[j + 1] == v[i])
					continue;
				if (OnSeg(v[i], a))
					e++;
			}
		}
		// cout << e << c << endl;
		printf("Case %d: There are %d pieces.
", ++cas, e + 2 - c);
	}
	return 0;
}