412      技术社区[云栖]

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

  上一篇： 315，这是一场神奇的晚会

  下一篇： TCPL 阅读笔记 Chapter1