程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1705 Count the grid &amp; jisuanke 35 三角形內點

HDU 1705 Count the grid &amp; jisuanke 35 三角形內點

編輯：C++入門知識

HDU 1705 Count the grid & jisuanke 35 三角形內點

題意：

給出一個三角形，求三角形內的整點；
皮克定理：S=a/2+b-1; S為多邊形面積；a為多邊形邊上的點； b為多邊形內的點；
a為邊上的點可以由歐幾裡得定理gcd(x1-x0,y1-y0)求得點數；

另編程網站計蒜客35題也是一樣的求法，只不過給出兩點，實際寫的話改成注釋的那塊就可以，鏈接：click here

代碼：

#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
#define lowbit(a) a&-a
#define Max(a,b) a>b?a:b
#define Min(a,b) a>b?b:a
#define mem(a,b) memset(a,b,sizeof(a))
int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};
const double eps = 1e-6;
const double Pi = acos(-1.0);
static const int inf= ~0U>>2;
static const int N=30010;
int scan()
{
    int res = 0, flag = 0;
    char ch;
    if((ch = getchar()) == '-') flag = 1;
    else if(ch >= '0' && ch <= '9') res = ch - '0';
    while((ch = getchar()) >= '0' && ch <= '9')
        res = res * 10 + (ch - '0');
    return flag ? -res : res;
}
void out(int a)
{
    if(a < 0)
    {
        putchar('-');
        a = -a;
    }
    if(a >= 10) out(a / 10);
    putchar(a % 10 + '0');
}
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
struct point
{
    int x,y;
} p[1000],pp[1000];
int acoss(point p1,point p2,point p0)
{
    return abs((p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x));
}
int main()
{
    int  a,area,ans;
    while(cin>>p[0].x>>p[0].y>>p[1].x>>p[1].y>>p[2].x>>p[2].y)
   {
          //while(cin>>p[1].x>>p[1].y>>p[2].x)
          // {
        //p[0].x=0,p[0].y=0,p[2].y=0;
        if(!p[0].x&&!p[0].y&&!p[1].x&&!p[1].y&&!p[2].x&&!p[2].y)break;
        pp[0].x=abs(p[0].x-p[1].x);
        pp[0].y=abs(p[0].y-p[1].y);
        pp[1].x=abs(p[1].x-p[2].x);
        pp[1].y=abs(p[1].y-p[2].y);
        pp[2].x=abs(p[0].x-p[2].x);
        pp[2].y=abs(p[0].y-p[2].y);
        a=gcd(pp[0].x,pp[0].y)+gcd(pp[1].x,pp[1].y)+gcd(pp[2].x,pp[2].y);
        area=acoss(p[1],p[2],p[0]);//求S
        ans=(area-a+2)/2;
        printf(%d
,ans);
    }
    return 0;
}