首页 > 代码库 > HDU 1665 - Different Digits(几何 + 欧拉定理)
HDU 1665 - Different Digits(几何 + 欧拉定理)
题意:在一个平面上,给定一个由 n 个点(4 <= n <= 300)组成的一封闭笔画图形(第一个端点与第 n 个端点重合),求这个图形将平面分成几个部分。
需要用到欧拉定理;
欧拉定理:设图的顶点数为 v ,边数(三维中为棱的个数)为 e ,面数为 f ,则v + f - e = 2.
则若求面数,只要求出顶点数 v 和边数 e,即能得出答案 f = e + 2 - v.
(注意:这里的边数 e,是指的单独一条线段,若中间被点分隔开,则算作多条线段而非一条)
具体处理如下:
1、先枚举任意两条画出的线段,看是否产生了新的交点,产生了即存入新的点数组中;
2、将产生的交点去重(可能出现三条及以上直线交于一点的情况);
3、边数 e 初始必为 n - 1(因为起点和终点重合),然后再统计新的交点断开产生的新边;
4、根据顶点数和边数算出答案即可.
套用几何模板,代码如下(部分注释注明了函数功能):
#pragma comment(linker, "/STACK:102400000, 102400000") #include<cstdio> #include<cstring> #include<cctype> #include<cstdlib> #include<cmath> #include<iostream> #include<sstream> #include<iterator> #include<algorithm> #include<string> #include<vector> #include<set> #include<map> #include<deque> #include<queue> #include<stack> #include<list> #define fin freopen("in.txt", "r", stdin) #define fout freopen("out.txt", "w", stdout) #define pr(x) cout << #x << " : " << x << " " #define prln(x) cout << #x << " : " << x << endl #define Min(a, b) a < b ? a : b #define Max(a, b) a < b ? b : a typedef long long ll; typedef unsigned long long llu; const int INT_INF = 0x3f3f3f3f; const int INT_M_INF = 0x7f7f7f7f; const ll LL_INF = 0x3f3f3f3f3f3f3f3f; const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f; const double pi = acos(-1.0); const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1}; const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1}; const int MOD = 10000; using namespace std; #define NDEBUG #include<cassert> const int MAXN = 300 + 10; const int MAXT = 10000 + 10; struct Point{ double x, y; Point(double x = 0, double y = 0) : x(x), y(y) {} }; typedef Point Vector; Vector operator + (Vector A, Vector B) {return Vector(A.x + B.x, A.y + B.y);} Vector operator - (Point A, Point 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);} bool operator < (const Point &a, const Point &b){ return a.x < b.x || (a.x == b.x && a.y < b.y); } const double EPS = 1e-8; int dcmp(double x){ 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 Cross(Vector A, Vector B) {return A.x * B.y - B.x * A.y;} //求两条线段的交点,第一条线段的起点为P,向量为V,第二条为Q和w(调用前保证有交点) Point GetLineIntersection(Point P, Vector v, Point Q, Vector w){ Vector u = P - Q; double t = Cross(w, u) / Cross(v, w); return P + v * t; } //判断a1a2与b1b2两条线段是否有交点 bool SegmentProperIntersection(Point &a1, Point &a2, Point &b1, Point &b2){ double c1 = Cross(a2 - a1, b1 - a1); double c2 = Cross(a2 - a1, b2 - a1); double c3 = Cross(b2 - b1, a1 - b1); double c4 = Cross(b2 - b1, a2 - b1); return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0; } //判断p是否在a1a2线段上(端点处不算) bool OnSegment(Point p, Point a1, Point a2){ return dcmp(Cross(a1 - p, a2 - p)) == 0 && dcmp(Dot(a1 - p, a2 - p)) < 0; } Point p[MAXN]; //输入的点 Point v[MAXN * MAXN]; //输入的点,以及线段相交出的点 //欧拉定理:平面图的顶点数为 v ,边数(三维中为棱的个数)为 e ,面数为 f ,则v + f - e = 2 //答案为 f = e + 2 - v int main(){ int n, kase = 0; while(scanf("%d", &n) == 1 && n){ for(int i = 0; i < n; ++i){ scanf("%lf%lf", &p[i].x, &p[i].y); v[i] = p[i]; } int c = n - 1, e = n - 1; //枚举每两条线段,检查是否相交,若相交则加入 c 数组 for(int i = 0; i < n - 1; ++i) for(int j = i + 1; j < n - 1; ++j) if(SegmentProperIntersection(p[i], p[i + 1], p[j], p[j + 1])) v[c++] = GetLineIntersection(p[i], p[i + 1] - p[i], p[j], p[j + 1] - p[j]); //去除重复相交的顶点 sort(v, v + c); c = unique(v, v + c) - v; //若新加入的点分割了原来的线段,则边数增加 for(int i = 0; i < c; ++i) for(int j = 0; j < n - 1; ++j) if(OnSegment(v[i], p[j], p[j + 1])) ++e; printf("Case %d: There are %d pieces.\n", ++kase, e + 2 - c); } return 0; }
HDU 1665 - Different Digits(几何 + 欧拉定理)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。