首页 > 代码库 > POJ--2284--That Nice Euler Circuit【平面图欧拉公式】
POJ--2284--That Nice Euler Circuit【平面图欧拉公式】
链接:http://poj.org/problem?id=2284
题意:一个自己主动绘图的机器在纸上(无限大)绘图,笔尖从不离开纸,有n个指令,每一个指令是一个坐标,由于笔尖不离开纸,所以相邻的坐标会连有一条直线,最后画笔再回到起始点。
所以这个图是一个连通图,而且画笔走过的路径是一个欧拉回路。
如今问题来了。这个图形将平面分成了几部分。
思路:题目说明确一些就是告诉你一些几何信息问平面被分成了几部分。能够用欧拉公式来做
欧拉公式:如果图的顶点个数为n,边数为m,区域数位r,则有 n - m + r = 2,前提必须是连通图
知道随意两个就能求第三个
#include<cstring> #include<string> #include<fstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cctype> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #include<functional> #include<cmath> using namespace std; #define PI acos(-1.0) #define MAXN 90010 #define eps 1e-7 #define INF 0x3F3F3F3F //0x7FFFFFFF #define LLINF 0x7FFFFFFFFFFFFFFF #define seed 1313131 #define MOD 1000000007 #define ll long long #define ull unsigned ll #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 struct Point{ //点 double x, y; Point(double a = 0, double b = 0){ x = a; y = b; } }; struct LineSegment{ //线段 Point s, e; LineSegment(Point a, Point b){ s = a; e = b; } }; struct Line{ //直线 double a, b, c; }; bool operator < (Point p1, Point p2){ return (p1.x < p2.x || p1.x == p2.x) && p1.y < p2.y; } bool operator == (Point p1, Point p2){ return fabs(p1.x - p2.x) < eps && fabs(p1.y - p2.y) < eps; } bool Online(LineSegment l, Point p){ //推断点是否在线段上 return fabs((l.e.x - l.s.x) * (p.y - l.s.y) - (p.x - l.s.x) * (l.e.y - l.s.y)) < eps && (p.x - l.s.x) * (p.x - l.e.x) < eps && (p.y - l.s.y) * (p.y - l.e.y) < eps; } Line MakeLine(Point p1, Point p2){ //将线段延长为直线 Line l; if(p2.y > p1.y){ l.a = p2.y - p1.y; l.b = p1.x - p2.x; l.c = p1.y * p2.x - p1.x * p2.y; } else{ l.a = p1.y - p2.y; l.b = p2.x - p1.x; l.c = p1.x * p2.y - p1.y * p2.x; } return l; //返回直线 } bool LineIntersect(Line l1, Line l2, Point &p){ //推断直线是否相交。并求出交点p double d = l1.a * l2.b - l2.a * l1.b; if(fabs(d) < eps) return false; //求交点 p.x = (l2.c * l1.b - l1.c * l2.b) / d; p.y = (l2.a * l1.c - l1.a * l2.c) / d; return true; } bool LineSegmentIntersect(LineSegment l1, LineSegment l2, Point &p){ //推断线段是否相交 Line a, b; a = MakeLine(l1.s, l1.e), b = MakeLine(l2.s, l2.e); //将线段延长为直线 if(LineIntersect(a, b, p)) //假设直线相交 return Online(l1, p) && Online(l2, p); //推断直线交点是否在线段上,是则线段相交 else return false; } bool cmp(Point a, Point b){ if(fabs(a.x - b.x) < eps) return a.y < b.y; else return a.x < b.x; } Point p[MAXN], Intersection[MAXN]; int N, m, n; int main(){ int i, j, cas = 1; while(scanf("%d", &N), N){ m = n = 0; for(i = 0; i < N; i++){ scanf("%lf%lf", &p[i].x, &p[i].y); } for(i = 0; i < N; i++){ for(j = 0; j < N; j++){ LineSegment l1(p[i], p[(i + 1) % N]), l2(p[j], p[(j + 1) % N]); Point p; if(LineSegmentIntersect(l1, l2, p)) Intersection[n++] = p; //记录交点 } } sort(Intersection, Intersection + n, cmp); n = unique(Intersection, Intersection + n) - Intersection; for(i = 0; i < n; i++){ for(j = 0; j < N; j++){ LineSegment t(p[j], p[(j + 1) % N]); if(Online(t, Intersection[i]) && !(t.s == Intersection[i])) //若有交点落在边上,则该边分裂成两条边 m++; } } printf("Case %d: There are %d pieces.\n", cas++, 2 - n + m); } return 0; }
POJ--2284--That Nice Euler Circuit【平面图欧拉公式】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。