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