题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1665
题目:
一笔画,问能把平面划分成多少个区域
解题思路:
根据欧拉公式可知,只需要求出V和E,平面数目自然就能得出:
计算新顶点:在原n-1个顶点的基础上,再加上每条线段和它后面的线段规范相交(交点不是端点)的交点即可,可能会有重复的交点,记得去重
计算新边:在原n-1条边的基础上,再加上每个顶点对边的贡献,只要这个顶点在原始的n-1条边上(不在边的端点上),就有贡献。
学的太死了,不会应用,欧拉公式也忘了QAQ。
ac代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 305;
const double eps = 1e-6;//eps用于控制精度,或者更高精度
const double pi = acos(-1.0);//pi
struct Point//点或向量
{
double x, y;
Point(double x = 0, double y = 0) :x(x), y(y) {}
friend bool operator < (Point a, Point b)
{
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
};
typedef Point Vector;
Vector operator + (Vector a, Vector b)//向量加法
{
return Vector(a.x + b.x, a.y + b.y);
}
Vector operator - (Vector a, Vector b)//向量减法
{
return Vector(a.x - b.x, a.y - b.y);
}
Vector operator * (Vector a, double p)//向量数乘
{
return Vector(a.x * p, a.y * p);
}
Vector operator / (Vector a, double p)//向量数除
{
return Vector(a.x / p, a.y / p);
}
int dcmp(double x)//精度三态函数(>0,<0,=0)
{
if (fabs(x) < eps)return 0; //等于
else return x < 0 ? -1 : 1;//小于,大于
}
bool operator == (const Point &a, const Point &b)//向量相等
{
return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;
}
double Dot(Vector a, Vector b)//点积
{
return a.x * b.x + a.y * b.y;
}
double Length(Vector a)//模
{
return sqrt(Dot(a, a));
}
double Angle(Vector a, Vector b)//夹角,弧度制
{
return acos(Dot(a, b) / Length(a) / Length(b));
}
double Cross(Vector a, Vector b)//外积
{
return a.x * b.y - a.y * b.x;
}
Vector Rotate(Vector a, double rad)//逆时针旋转rad弧度
{
return Vector(a.x*cos(rad) - a.y*sin(rad), a.x*sin(rad) + a.y*cos(rad));
}
Point GetLineIntersection(Point P, Vector v, Point Q, Vector w)//两直线的交点
{
Vector u = P - Q;//QP
double t = Cross(w, u) / Cross(v, w);
return P + v * t;
}
bool SegmentProperIntersection(Point a1, Point a2, Point b1, Point b2)
{
double c1 = Cross(a2 - a1, b1 - a1), c2 = Cross(a2 - a1, b2 - b1),
c3 = Cross(b2 - b1, a1 - b1), c4 = Cross(b2 - b1, a2 - b1);
return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;
}
bool Onsegment(Point p, Point a1, Point a2)
{
return dcmp(Cross(a1 - p, a2 - p)) == 0 && dcmp(Dot(a1 - p, a2 - p)) < 0;
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
int n, casee = 0;
while(scanf("%d", &n) && n != 0)
{
Point P[maxn], allp[maxn * maxn];
for(int i = 0; i < n; i++)
{
scanf("%lf %lf", &P[i].x, &P[i].y);
allp[i] = P[i];
}
int v = n - 1, e = n - 1;
//增加新顶点:
for(int i = 0; i < n - 1; i++)
for(int j = i + 1; j < n-1; j++)//j + 1 最大n-1
if(SegmentProperIntersection(P[i], P[i + 1], P[j], P[j + 1]))//当前点和下一个点构成的边和它后面的边有无不是端点的交点
allp[v++] = GetLineIntersection(P[i], P[i + 1] - P[i], P[j], P[j + 1] - P[j]);
sort(allp, allp + v);
v = unique(allp, allp + v) - allp;
//增加新边:
for(int i = 0; i < v; i++) //当前点在原始边上且不在端点
for(int j = 0; j < n - 1; j++)
if(Onsegment(allp[i], P[j], P[j + 1])) e++; //j + 1最大是n-1
printf("Case %d: There are %d pieces.\n", ++casee, e + 2 - v);
}
return 0;
}