首页 > 代码库 > poj2284 That Nice Euler Circuit(欧拉公式)
poj2284 That Nice Euler Circuit(欧拉公式)
题目链接:poj2284 That Nice Euler Circuit
欧拉公式:如果G是一个阶为n,边数为m且含有r个区域的连通平面图,则有恒等式:n-m+r=2。
欧拉公式的推广: 对于具有k(k≥2)个连通分支的平面图G,有:n-m+r=k+1。
题意:给出连通平面图的各顶点,求这个欧拉回路将平面分成多少区域。
题解:根据平面图的欧拉定理“n-m+r=2”来求解区域数r。
顶点个数n:两两线段求交点,每个交点都是图中的顶点。
边数m:在求交点时判断每个交点落在第几条边上,如果一个交点落在一条边上,这条边就分裂成两条边,边数加一。
学习之路漫漫啊。。
看懂了书上例题再敲的,我基础差就是累哦、、
1 #include<cstdio> 2 #include<cmath> 3 #include<queue> 4 #include<cstring> 5 #include<algorithm> 6 using namespace std; 7 8 const double eps = 1e-9; 9 const int N = 90001;10 11 struct point{//点12 double x, y;13 point(double _x = 0, double _y = 0): x(_x), y(_y){}14 };15 16 struct lineSegment{//线段17 point s, e;18 lineSegment(point s, point e): s(s), e(e){}19 };20 struct line{//直线21 double a, b, c;22 };23 bool operator < (point p1, point p2){24 return p1.x < p2.x || p1.x == p2.x && p1.y < p2.y;25 }26 bool operator == (point p1, point p2){27 return abs(p1.x - p2.x) < eps && abs(p1.y - p2.y) < eps;28 }29 bool onLine(lineSegment l, point p){//判断点是否在线段上30 return abs((l.e.x - l.s.x)*(p.y - l.s.y) - (p.x - l.s.x)*(l.e.y - l.s.y)) < eps //点在直线上31 && (p.x - l.s.x) * (p.x - l.e.x) < eps && (p.y - l.s.y) * (p.y - l.e.y) < eps;//点在线段内32 }33 line make_Line(point p1, point p2){//将线段延长为直线34 line l;35 l.a = (p2.y > p1.y) ? p2.y - p1.y : p1.y - p2.y;36 l.b = (p2.y > p1.y) ? p1.x - p2.x : p2.x - p1.x;37 l.c = (p2.y > p1.y) ? p1.y * p2.x - p1.x * p2.y : p1.x * p2.y - p1.y * p2.x;38 return l;39 }40 //判断直线是否相交,并求交点p41 bool line_Intersect(line l1, line l2, point &p){42 double d = l1.a * l2.b - l2.a * l1.b;43 if(abs(d) < eps) return false; //叉积为0,平行或重合44 p.x = (l2.c * l1.b - l1.c * l2.b) /d;45 p.y = (l2.a * l1.c - l1.a * l2.c) /d;46 return true;47 }48 //判断线段是否相交49 bool lineSegment_Intersect(lineSegment l1, lineSegment l2, point &p){50 line a, b;51 a = make_Line(l1.s, l1.e);//将线段延长为直线52 b = make_Line(l2.s, l2.e);53 if(line_Intersect(a, b, p))//如果直线相交54 //判断直线交点是否在线段上,是则线段相交55 return onLine(l1, p) && onLine(l2, p);56 else return false;57 }58 59 point p[N], intersection[N];60 int n, m;61 62 int main(){63 int nn, i, j, kase = 1;64 while(scanf("%d", &nn) && nn){65 n = m = 0;66 for(i = 0; i < nn; ++i)67 scanf("%lf %lf", &p[i].x, &p[i].y);68 for(i = 0; i < nn; ++i){69 for(j = 0; j < nn; ++j){70 if(i == j) continue;71 lineSegment l1(p[i], p[(i+1)%nn]), l2(p[j], p[(j+1)%nn]);72 point v;73 if(lineSegment_Intersect(l1, l2, v))74 intersection[n++] = v;//记录交点75 }76 }77 sort(intersection , intersection + n);78 //移除重复点79 n = unique(intersection, intersection + n) - intersection;80 for(i = 0; i < n; ++i){81 for(j = 0; j < nn; ++j){82 lineSegment l3(p[j], p[(j+1)%nn]);83 //若有交点落在边上,则该边分裂成两条边84 if(onLine(l3, intersection[i]) && !(l3.s == intersection[i]))85 m++;86 }87 }88 printf("Case %d: There are %d pieces.\n", kase++, 2 + m - n);89 }90 return 0;91 }
poj2284 That Nice Euler Circuit(欧拉公式)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。