【POJ 2954】 Triangle
很涨姿势的一道题 涉及三点 1.三角形算法 已知三点 S = (AB X BC)/2 (PS:海伦公式<已知三边> S = sqrt(p(p-a)(p-b)(p-c) p = (a+b+c)/2) 2.已知两点求两点间格点 即为求两点横纵坐标差的最大公倍数(-1—–不包含顶点) (gcd( abs(x2-x1),abs(y2-y1) ) (-1)) 3.格点多边形的面积 s = d/2+t-1(d->多边形边界的格点数 t->多边形内部格点数 本题求t 移项即可)
代码如下
#include <cstdio>#include <cmath>using namespace std;int gcd(int a,int b){int r;while(b){r = b;b = a%b;a = r;}return a;}int main(){int x1,y1,x2,y2,x3,y3,s;”,&x1,&y1,&x2,&y2,&x3,&y3) && (x1 || y1 || x2 || y2 || x3 || y3)) {s = abs((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1));printf(“%d\n”,(s+2-gcd(abs(x2-x1),abs(y2-y1))-gcd(abs(x3-x2),abs(y3-y2))-gcd(abs(x1-x3),abs(y1-y3)))/2); }return 0;}
，所有的赏赐都只是被用来奖励工作成果的。
