数论问题

这一次我们来讨论讨论计算几何问题

计算几何说难也难，说不难也不难，关键是模板，计算几何有许多的模板，而且许多的问题都要在纸上先写出自己的想法，推导完成后，再转换为代码，其中向量是最为重要的的一个概念。
话不多说先上题目，通过题目去体会计算几何的魅力；
题目：
链接: poj 1269.
这一道题就用到很多模板：

struct point 
{
	double x,y;//点坐标
	point (double x=0,double y=0):x=(x),y=(y){} 
}; 
typedef point vector;//向量坐标
point read_point()//点的读入 
{
	double x,y;
	scanf("%lf %lf",&x,&y);
	return point(x,y);
}
vector operator-(point a,point b) //向量加减 
{
	return vector(a.x-b.x,a.y-b.y);
}


double cross(vector a,vector b)//叉积，注意这里是向量 
{
	return a.x*b.y-b.x*a.y;
} 

point point_inter(point p,vector v,point q,vector w)
{
	vector u=p-q;
	double t=cross(w,u)/cross(v,w);
	return p+v*t;
} 

这里就是这道题目所用到的模板：
我的代码：

#include<stdio.h>
#include<math.h>
struct point
{
	double x,y;
	point(double x=0,double y=0):x(x),y(y){};
};
typedef point vector; 
point read_point()
{
	double x,y;
	scanf("%lf%lf",&x,&y);
	return point(x,y);	
}
vector operator-(point a,point b)
{
	return vector(a.x-b.x,a.y-b.y); 
}
vector operator*(vector a,double b)
{
	return vector(a.x*b,a.y*b); 
}
vector operator+(vector a,vector b)
{
	return vector(a.x+b.x,a.y*b.y); 
}
double Cross(vector a,vector b)
{
	return a.x*b.y-a.y*b.x;
}
point point_inter(point p,vector v,point q,vector w)
{
	vector u=p-q;
	double t=Cross(w,u)/Cross(v,w);
	return p+v*t;
}
int main()
{
	int k;
	scanf("%d",&k);
	point a1,a2,b1,b2;
	printf("INTERSECTING LINES OUTOUT\n");
	while(k--){
		a1=read_point();
		a2=read_point();
		b1=read_point();
		b2=read_point();
		vector a=a2-a1,b=b2-b1;
		if(Cross(a,b)==0){
			if(Cross(b1-a1,b2-a1)==0&&Cross(b1-a2,b2-a2)==0){
				printf("LINE\n");
			}
			else{
				printf("NONE\n");
			}
		} 
		else{
			point ans=point_inter(a1,a1-a2,b1,b1-b2);
			printf("POINT%.2f %.2f\n",ans.x,ans.y);
		}
	}
	printf("END OF OUTPUT");
	return 0;
} 

思路：这里有一个点就是如何去判断它平行，运用叉积的知识先去判断它是否平行，如果是再去判断是否共线，如果不是那就是相交。
（2）题目：
链接: hdu.
这一道题其实就是比较纯粹的数学题，求多边形的面积；
我的代码：

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
//把多边形变成一个一个的三角形，而且都已（0,0)为原点； 
struct point 
{
	int x,y;
}a[110];
double area(struct point q,struct point p)
{
	return q.x*p.y-p.x*q.y;//叉乘计算面积 
}
int main()
{
	int k;
	scanf("%d",&k);
	while(k){
		for(int i=0;i<k;i++){
			scanf("%d %d",&a[i].x,&a[i].y);
		} 
		double sum=area(a[k-1],a[0]);
		for(int i=1;i<k;i++){
			sum+=area(a[i],a[i-1]);//注意最后i==k-1 
		}
		printf("%.11f\n",fabs(sum*0.5));
		scanf("%d",&k);
	}
	return 0;
}

这里的原理是取（0，0）来分割多个三角形，运用叉乘去求三角形的有效面积，再求和；自己在纸上画一下就很清晰了；
’
本期就到这了，谢谢大家哈（最后说一句：一定一定要将纸上得出的解转换成算法）