閱讀412 返回首頁    go 阿裏雲 go 技術社區[雲棲]

POJ 2954 pick公式

這題用到了pick公式，area=on/2+in-1 on為在多邊形邊上的點數，in為在多邊形內的點數。叉積求多邊形麵積，gcd(x,y)為邊上的點數，x為相鄰兩點x差的絕對值，y同理。根據公式可求在多邊形內的點數。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int gcd(int a,int b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}
int ab(int a)
{
    return a>=0?a:-a;
}
int main()
{
    int x[3],y[3];
    while(cin>>x[0]>>y[0]>>x[1]>>y[1]>>x[2]>>y[2],!(!x[0]&&!x[1]&&!x[2]&&!y[0]&&!y[1]&&!y[2]))
    {
        int ep=0,area=0,in;
        for(int i=0; i<3; i++)
            area+=x[i]*y[(i+1)%3]-y[i]*x[(i+1)%3],
                  ep+=gcd(ab(x[i]-x[(i+1)%3]),ab(y[i]-y[(i+1)%3]));
        area=ab(area);
        in=area/2-ep/2+1;
        printf("%d\n",in);
    }
    return 0;
}


最後更新：2017-04-03 22:15:45

  上一篇：go 315，這是一場神奇的晚會
  下一篇：go TCPL 閱讀筆記 Chapter1