首页 > 代码库 > UVA LIVE-3263 - That Nice Euler Circuit

UVA LIVE-3263 - That Nice Euler Circuit

2024-07-23 10:45:45   218人阅读

画一个顶点为偶数的封闭的二维图，当然，这个图可以自交，给出画的过程中的一些轨迹点，求出这个图把二次元分成了几部分，例如三角形把二次元分成了两部分。

这个的话，有图中顶点数+部分数-棱数=2的定律，这是核心思想，也就是所谓的欧拉定律拓扑版，好吧，其实仔细想想也是能够想出这个规律来的。

做出这题纯属意外，由于给的点的坐标全是用整数表示，为了不用考虑精度问题，一开始，我就想只用这些点，就是说不再算出其它交点之类的，就把答案算出，

因为当前轨迹与之前轨迹无非三种情况：规范与不规范相交，不相交

不相交当然就不用管了，相交的话，考虑两种情况下的顶点、棱的数量变化

但是不知道是不是题意有些细节没理解到，还是有些特殊的图的情况没考虑到，用这种思路虽然代码比较精炼，但是一直wa

后来索性干脆把所有的顶点用行列式求出，然后再求棱，稍微想想可以知道，棱的数目是在轨迹数目的基础上加上在轨迹中间，即在轨迹上，不在轨迹两点的交点数目

这里就需要通过叉积判断点是否在轨迹中间，由于题中没有给出精度要求……如果不给一个精度，而直接用叉积为0判断点是否在轨迹所在的直线上的话，会wa

因为直接用0，相当于，精度就是double的精度，也就是1e-15，所以后来改成了1e-9然后就过了。

需要注意的是，在杭电上也有同样的题，但明显杭电的oj比UVA的渣，杭电的g++比c++的精度运算损失少，所以在杭电上交用这种不太好的方法写的代码，需要用g++交才能

过。

我的代码：

#include<iostream>
#include<map>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const double inf=1e4,eps=1e-9;
struct dot
{
	double x,y;
	dot(){}
	dot(double a,double b){x=a;y=b;}
	dot operator -(dot a){return dot(x-a.x,y-a.y);}
	friend bool operator <(dot a,dot b){return a.x!=b.x?a.x<b.x:a.y<b.y;}
	bool operator ==(dot a){return x==a.x&&y==a.y;}
	bool operator !=(dot a){return x!=a.x||y!=a.y;}
	double operator *(dot a){return x*a.y-y*a.x;}
	double dis(dot a){return sqrt(pow(x-a.x,2)+pow(y-a.y,2));}
};
bool isdil(dot a,dot b,dot c)
{
	return a.x<=max(b.x,c.x)&&
		   a.y<=max(b.y,c.y)&&
		   min(b.x,c.x)<=a.x&&
		   min(b.y,c.y)<=a.y&&
		   a!=b&&a!=c;
}
bool isdbl(dot a,dot b,dot c){return fabs((a-c)*(b-c))<eps&&isdil(a,b,c);}
dot cross(dot a,dot b,dot c,dot d)  
{
    double e,f,g,h,i,j,k,l,m;  
    e=b.y-a.y;f=a.x-b.x;g=a.x*b.y-a.y*b.x;  
    h=d.y-c.y;i=c.x-d.x;j=c.x*d.y-c.y*d.x;  
    k=dot(e,h)*dot(f,i);
	if(k==0)
		return dot(inf,inf);  
    l=dot(g,j)*dot(f,i);  
    m=dot(e,h)*dot(g,j);
    dot t=dot(l/k,m/k);
    return isdil(t,a,b)&&isdil(t,c,d)?t:dot(inf,inf);
}
int main()
{
	dot a[310],b[30000],t;
	int i,n,j,k,ans,T=0;
	while(cin>>n&&n)
	{
		for(i=0;i<n;i++)
		{
			cin>>a[i].x>>a[i].y;
			b[i]=a[i];
		}
		k=n;
		for(i=1;i<n;i++)
			for(j=i+2;j<n;j++)
			{
				t=cross(a[i-1],a[i],b[j-1],b[j]);
				if(t.x!=inf)
					b[k++]=t;
			}
		sort(b,b+k);
		k=unique(b,b+k)-b;
		ans=1+n-k;
			for(j=0;j<k;j++)
				for(i=1;i<n;i++)
				if(isdbl(b[j],a[i-1],a[i]))
					ans++;
		printf("Case %d: There are %d pieces.\n",++T,ans);
	}
}

原题：

Description

Download as PDF

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 integerN$ \ge$4, which is the number of instructions in the test case. The followingN 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 whenN 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.

\epsfbox{p3263.eps}

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.

UVA LIVE-3263 - That Nice Euler Circuit


联系
我们