POJ 2954 Triangle(求整顶点多边形包含的整点数)
http://poj.org/problem?id=2954
题意:
给你一个由3个整点构成的三角形,要你求出该三角形内部的整点个数.
分析:
由Pick定理,一个多边形如果每个顶点都由整点构成,该多边形的面积为S,该多边形边上的整点为L,内部的整点为N,则有:
N+L/2-1=S.
那么我们只要求出该三角形的面积和三角形边上到底有多少个整点即可. 面积直接用叉积求.下面求三角形各边上有多少个整点.
假设有一条由两个整点构成的线段,该线段该线段X方向的增量绝对值为DX, Y方向的增量绝对值为DY. 设线段内部(不含端点)整点个数为ans:
DX==DY==0时, ans=0
DX==0时, ans=DY-1(等价于gcd(DX,DY)-1
)
DY==0时, ans=DX-1 (等价于gcd(DX,DY)-1 )
DX!=0且DY!=0时, ans=gcd(DX,DY)-1
简单说明一下上面结论:
端点是整点的线段内部如果有整点, 那线段一定是被内部的整点均匀分割的.
假设线段内部有5个整点(这5个整点一定是均匀排列的),那么包括两端点共7个整点,线段被分成了6等份. 其实就是DX和DY分别被分成了6等份,那么说明DX和DY的最大公约数==6. 如果DX与DY的最大公约数==8,那么线段一定且最多能被分成8等份,且由于线段端点是整点,所以8等份的每个点都是整点.
AC代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct Point
{
double x,y;
Point(){}
Point(double x,double y):x(x),y(y){}
};
typedef Point Vector;
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-A.y*B.x;
}
double Area(Point A,Point B,Point C)
{
return fabs(Cross(A-B,B-C))/2;
}
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
int get_segment_point(Point A,Point B)//返回整点构成的线段内部的整点数
{
int dx=fabs(A.x-B.x),dy=fabs(A.y-B.y);
if(dx==0 && dy==0) return 0;
return gcd(dx,dy)-1;
}
int main()
{
int x1,y1,x2,y2,x3,y3;
while(scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3)==6)
{
if(x1==0&&y1==0&&x2==0&&y2==0&&x3==0&&y3==0) break;
Point A(x1,y1),B(x2,y2),C(x3,y3);
int S=Area(A,B,C);//面积
int L=3+get_segment_point(A,B)+get_segment_point(B,C)+get_segment_point(A,C);//边整点
printf("%d\n",S+1-L/2);
}
return 0;
}
分享到:
相关推荐
北大POJ1163-The Triangle 解题报告+AC代码
北大POJ1163-The Triangle
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ2002-Squares 解题报告+AC代码
poj分类poj分类poj分类poj分类
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
POJ 最接近点对问题 ACM北大 using namespace std; struct Point { float x; float y; };
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
poj1379 给予平面内一个点集; 使用模拟退火求出一个点使该点到上述点集内任意一点最短距离最长。
poj.grids.cn题型汇总 Dp状态设计与方程总结 ...最小逼近问题(求出两数之比最接近某数/两数之和等于某数等等) 方块消除游戏(某区间可以连续消去求最大效益) 资源分配问题 数字三角形问题 漂亮的打印
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 百练 题目分类 poj 百练 题目分类
POJ1083的代码,POJ1083的代码,POJ1083的代码
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj1125原创AC代码,用的是folyd算法,求出所有点之间的最短路径,再以此求出每个点到其他点的最长路径。。。