209      阿里云  技术社区[云栖]

POJ 1265 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 n,t,s=0;
    scanf("%d",&t);
    while(t--)
    {
        if(s)
            printf("\n");
        scanf("%d",&n);
        int ep=0,area=0,in,x,y,x1=0,y1=0,x2=0,y2=0;
        for(int i=0; i<n; i++)
        {
            scanf("%d%d",&x,&y);
            x1+=x,y1+=y;
            area+=x1*y2-y1*x2;
            x2=x1,y2=y1;
            ep+=gcd(ab(x),ab(y));
        }
        area=ab(area);
        in=area/2-ep/2+1;
        printf("Scenario #%d:\n%d %d %.1f\n",++s,in,ep,area/2.0);
    }
    return 0;
}

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

  上一篇： 杨氏矩阵查找

  下一篇： Eclipse的JSP页面提示Multiple annotations found at this line或者String cannot be resolved to a type