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\n", 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.\n", ++cas, e + 2 - c);
}
return 0;
}
版权声明：本文博客原创文章，博客，未经同意，不得转载。
