noj 1048 三角形所包围点的个数.txt

POJ上一些计算几何题的代码………………

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;

//三角形所包围点的个数 NOJ 1048
//通过求三角形的面积，求点的个数
/*
输入： 
0 0 1 0 0 1
0 0 5 0 0 5
0 0 0 0 0 0

输出：
0 
6
*/
double getmianji(int x1,int y1,int x2,int y2,int x3,int y3)
{
	//根据三个点的坐标求得三角形的面积
	return (double)((x1*y2+x2*y3+x3*y1-y1*x2-y2*x3-y3*x1)/2); 
}

int gys(int a,int b)
{	//求a,b的公约数
	if(a<b)
	{
		a+=b;
		b=a-b;
		a=a-b;
	}
	if(a==0) return b;
	else if(b==0) return a;
	else return gys(b,a%b);
}

int getbiandian(int x1,int y1,int x2,int y2)
{	//求以(x1,y1),(x2,y2)为端点的线段上的点的个数
	int x,y;
	x=abs(x1-x2);
	y=abs(y1-y2);
	return gys(x,y)-1;
}

double cal(int x1,int y1,int x2,int y2,int x3,int y3)
{
	double mianji,md1,md2,md3;
	mianji=fabs(getmianji(x1,y1,x2,y2,x3,y3));
	md1=getbiandian(x1,y1,x2,y2);
	md2=getbiandian(x2,y2,x3,y3);
	md3=getbiandian(x3,y3,x1,y1);
	//所包围点的个数=面积-顶点的个数/6-边上点的个数/2；
	return mianji-1/2-(md1+md2+md3)/2;
}
int main()
{
	int x1,y1,x2,y2,x3,y3;
	scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3);
	while(!(x1==0&&y1==0&&x2==0&&y2==0&&x3==0&&y3==0))
	{
		cout<<(int)cal(x1,y1,x2,y2,x3,y3)<<endl;
		scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3);
	}
	return 0;
}