Triangle
题意:给你一个三角形三个点的坐标,问你三角形内部有多少点
思路:先利用多边形面积公式求出三角形面积,再gcd(detax,detay)之和求出边上有多少点,最后利用皮克定理求出内部有多少点,s=in+1+on/2;
1 // 2 // Created by HJYL on 2020/2/4. 3 // 4 #include<iostream> 5 #include<cstring> 6 #include<cstdio> 7 #include<cstring> 8 #include<math.h> 9 #include<algorithm> 10 using namespace std; 11 const double eps=1e-8; 12 const int maxn=1e6+5; 13 int gcd(int a,int b) { 14 while (b) { 15 int r = b; 16 b = a % b; 17 a = r; 18 } 19 return a; 20 } 21 struct Point{ 22 int x,y; 23 Point(int x=0,int y=0):x(x),y(y){} 24 Point operator - (Point const &b)const 25 { 26 return Point(x-b.x ,y-b.y); 27 } 28 bool operator < (Point const &c)const{ 29 if(x==c.x) 30 return y<c.y; 31 return x<c.x; 32 } 33 }; 34 double Cross(Point A,Point B) 35 { 36 return (A.x*B.y)-(A.y*B.x); 37 } 38 long long PolygonArea(Point* p, int n) {//p为端点集合,n为端点个数 39 long long s = 0; 40 for (int i = 1; i < n - 1; ++i) 41 s += Cross(p[i] - p[0], p[i + 1] - p[0]); 42 return s<0?-s:s; 43 } 44 int main() 45 { 46 Point p[3]; 47 while(~scanf("%d%d%d%d%d%d",&p[0].x,&p[0].y,&p[1].x,&p[1].y,&p[2].x,&p[2].y)) 48 { 49 if(p[0].x==0&&p[1].x==0&&p[2].x==0&&p[0].y==0&&p[1].y==0&&p[2].y==0) 50 break; 51 long long s=PolygonArea(p,3);//s=on/2+in-1 52 int on=0; 53 for(int i=1;i<3;i++) 54 { 55 on+=gcd(abs(p[i].x-p[i-1].x),abs(p[i].y-p[i-1].y)); 56 } 57 on+=gcd(abs(p[2].x-p[0].x),abs(p[2].y-p[0].y)); 58 int in=(s+2-on)/2; 59 printf("%d ",in); 60 61 } 62 return 0; 63 }