POJ2284 That Nice Euler Circuit (欧拉公式)(计算几何 线段相交问题)

That Nice Euler Circuit

Time Limit: 3000MS   Memory Limit: 65536K
Total Submissions: 1977   Accepted: 626

Description

Little Joey invented a scrabble machine that he called Euler, after the great mathematician. In his primary school Joey heard about the nice story of how Euler started the study about graphs. The problem in that story was - let me remind you - to draw a graph on a paper without lifting your pen, and finally return to the original position. Euler proved that you could do this if and only if the (planar) graph you created has the following two properties: (1) The graph is connected; and (2) Every vertex in the graph has even degree.

Joey‘s Euler machine works exactly like this. The device consists of
a pencil touching the paper, and a control center issuing a sequence of
instructions. The paper can be viewed as the infinite two-dimensional
plane; that means you do not need to worry about if the pencil will ever
go off the boundary.

In the beginning, the Euler machine will issue an instruction of the
form (X0, Y0) which moves the pencil to some starting position (X0,
Y0). Each subsequent instruction is also of the form (X‘, Y‘), which
means to move the pencil from the previous position to the new position
(X‘, Y‘), thus draw a line segment on the paper. You can be sure that
the new position is different from the previous position for each
instruction. At last, the Euler machine will always issue an instruction
that move the pencil back to the starting position (X0, Y0). In
addition, the Euler machine will definitely not draw any lines that
overlay other lines already drawn. However, the lines may intersect.

After all the instructions are issued, there will be a nice picture
on Joey‘s paper. You see, since the pencil is never lifted from the
paper, the picture can be viewed as an Euler circuit.

Your job is to count how many pieces (connected areas) are created on the paper by those lines drawn by Euler.

Input

There
are no more than 25 test cases. Ease case starts with a line containing
an integer N >= 4, which is the number of instructions in the test
case. The following N pairs of integers give the instructions and appear
on a single line separated by single spaces. The first pair is the
first instruction that gives the coordinates of the starting position.
You may assume there are no more than 300 instructions in each test
case, and all the integer coordinates are in the range (-300, 300). The
input is terminated when N is 0.

Output

For each test case there will be one output line in the format

Case x: There are w pieces.,

where x is the serial number starting from 1.

Note: The figures below illustrate the two sample input cases.

Sample Input

5
0 0 0 1 1 1 1 0 0 0
7
1 1 1 5 2 1 2 5 5 1 3 5 1 1
0

Sample Output

Case 1: There are 2 pieces.
Case 2: There are 5 pieces.欧拉公式:对任意平面图,顶点数n,边数m且含有r个区域,则有 n-m+r=2.这题最难得还是判断两线段是否相交并求出相交点。
#include<cstdio>
#include<cstring>
#include<stdlib.h>
#define inf 0xffffff
#include<iostream>
#include<cmath>
#define NUM 22
#include <algorithm>
using namespace std;

const double eps=1e-6;
struct point {
    double x,y;
    point(double a=0,double b=0) {
        x=a;
        y=b;
    }
};
bool operator< (point a, point b) {
    return a.x<b.x||a.x==b.x&&a.y<b.y;
}
bool operator == (point a,point b) {
    return abs(a.x-b.x)<eps&&abs(a.y-b.y)<eps;
}
struct Lineseg {
    point s,e;
    Lineseg(point a, point b) {
        s=a;
        e=b;
    }
};
struct Line {
    double a,b,c;
};
bool online(Lineseg L,point p) { //判断p是否在线段L上
    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&&(p.x-L.s.x)*(p.x-L.e.x)<eps&&(p.y-L.s.y)*(p.y-L.e.y)<eps;
}
Line Makeline(Lineseg tmp) { //线段L变成L
    Line L;
    int x1=tmp.s.x;
    int y1=tmp.s.y;
    int x2=tmp.e.x;
    int y2=tmp.e.y;
    if(y2-y1>0) {
        L.a=(y2-y1);
        L.b=(x1-x2);
        L.c=(x2*y1-x1*y2);
    } else {
        L.a=(y1-y2);
        L.b=(x2-x1);
        L.c=(x1*y2-x2*y1);
    }
    return L;
}
bool Lineinter(Line x,Line y,point &q) { //直线X,Y相交于点q
    double d=x.a*y.b-y.a*x.b;
    if(abs(d)<eps)
        return false;
    q.x=(y.c*x.b-x.c*y.b)/d;
    q.y=(y.a*x.c-x.a*y.c)/d;
    return 1;
}

bool Lineseginter(Lineseg aa,Lineseg bb,point &q) { //线段aa,bb如果相交则返回交点q
    Line a,b;
    a=Makeline(aa);
    b=Makeline(bb);
    if(Lineinter(a,b,q))
        return online(aa,q)&&online(bb,q);
    else
        return false;
}
bool cmp(point a ,point b) {
    if(a.x==b.x)
        return a.y<b.y;
    else
        return a.x<b.x;
}
point p[96003];
point inter[98000];
int N;
int main() {
    int m,n;
    int T=0;
    while(scanf("%d",&N),N) {
        m=n=0;
        int cnt=0;
        for(int i=0; i<N; i++)
            scanf("%lf %lf",&p[i].x,&p[i].y);
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                Lineseg L1(p[i],p[(i+1)%N]),L2(p[j],p[(j+1)%N]);
                point q;
                if(Lineseginter(L1,L2,q))
                    inter[cnt++]=q;
            }
        }
        sort(inter,inter+cnt,cmp);
        n=unique(inter,inter+cnt)-inter;//去重复的点
        for(int i=0; i<n; i++) {
            for(int j=0; j<N; j++) {
                Lineseg t(p[j],p[(j+1)%N]);
                if(online(t,inter[i])&&!(t.s==inter[i]))m++;
            }
        }
        T++;
        printf("Case %d: There are %d pieces.\n",T,m+2-n);//欧拉定理
    }
    return 0;
}
时间: 10-12

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:在求交点时判断每个交点落在第几条边上,如果一个交点落在

poj1039(计算几何)线段相交

题意:给一个管道求光线能穿到的最大x坐标. 解法:通过旋转光线一定可以使得光线接触一个上点和一个下点.枚举接触的上下点,然后逐一判断光线是否穿过每个拐点面.碰到一个拐点面没有穿过的,则是因为与其左边线段相交,求出直线与线段交点更新答案即可.不想交则说明在前一个拐点已经穿出去了. 代码: /****************************************************** * author:xiefubao ********************************

UVALive - 3263 - That Nice Euler Circuit (计算几何~~)

UVALive - 3263 That Nice Euler Circuit Time Limit: 3000MS   Memory Limit: Unknown   64bit IO Format: %lld & %llu Submit Status Description Little Joey invented a scrabble machine that he called Euler, after the great mathematician. In his primary sch

德莱联盟 计算几何 线段相交

难度:1 描述 欢迎来到德莱联盟.... 德莱文... 德莱文在逃跑,卡兹克在追.... 我们知道德莱文的起点和终点坐标,我们也知道卡兹克的起点和 终点坐标,问:卡兹克有可能和德莱文相遇吗?,并且保证他们走的都是直线. 输入 几组数据,一个整数T表示T组数据每组数据 8个实数,分别表示德莱文的起点和终点坐标,以及卡兹克的起点和终点坐标 输出 如果可能 输出 Interseetion,否则输出 Not Interseetion 样例输入 2 -19.74 7.14 22.23 -27.45 -38

POJ 3347 Kadj Squares (计算几何+线段相交)

题意:从左至右给你n个正方形的边长,接着这些正方形都按照旋转45度以一角为底放置坐标轴上,最左边的正方形左端点抵住y轴,后面的正方形依次紧贴前面所有正方形放置,问从上方向下看去,有哪些正方形是可以被看到的(如图) 题解:首先我们找到每个正方形左右端点的坐标转化为一条线段,接着我们寻找哪些线段被其他某些条线段覆盖,这些被覆盖的线段就不能被看到 寻找被覆盖的线段利用区贪心间,我们按照左端点升序.左端点相同右端点降序排序,则左端点一定被前面的线段覆盖,接着对于右端点使用单调栈的思想寻找可以看到的线段就

UVALive 3263 That Nice Euler Circuit 计算几何欧拉定理

欧拉定理:P+F-E=2 That Nice Euler Circuit Time Limit: 3000MS   Memory Limit: Unknown   64bit IO Format: %lld & %llu Submit Status Description Little Joey invented a scrabble machine that he called Euler, after the great mathematician. In his primary schoo

POJ--2284--That Nice Euler Circuit【平面图欧拉公式】

链接:http://poj.org/problem?id=2284 题意:一个自己主动绘图的机器在纸上(无限大)绘图,笔尖从不离开纸,有n个指令,每一个指令是一个坐标,由于笔尖不离开纸,所以相邻的坐标会连有一条直线,最后画笔再回到起始点. 所以这个图是一个连通图,而且画笔走过的路径是一个欧拉回路. 如今问题来了.这个图形将平面分成了几部分. 思路:题目说明确一些就是告诉你一些几何信息问平面被分成了几部分.能够用欧拉公式来做 欧拉公式:如果图的顶点个数为n,边数为m,区域数位r,则有 n - m

平面上欧拉定理:poj 2284( LA 3263 ) That Nice Euler Circuit

3263 - That Nice Euler Circuit Time limit: 3.000 seconds Description Little Joey invented a scrabble machine that he called Euler, after the great mathematician. In his primary school Joey heard about the nice story of how Euler started the study abo

【UVA】1342 - That Nice Euler Circuit(几何+欧拉定理)

E 为边数 ,V 为点数,F为面数 那么 F = E + 2 - V(其中包括了一个无限大的面) 这道题被自己的习惯坑了一下#define MAXD 300 + 10 和#define MAXD 310 是不一样的 14113235 1342 That Nice Euler Circuit Accepted C++ 0.082 2014-08-29 15:12:20 自己的代码: #include<cstdio> #include<cstring> #include<iost