Area POJ - 1265 [Pick定理]

Area POJ - 1265

题意: 给定一个多边形的相邻点的dx,dy. 求在多边形内部点的个数in,多边形边界上的个数on,多边形的面积s

思路: s代表多边形面积  , on=abs(gcd(dx,dy)), in=(2s+2-on)/2; 求面积的时候/2 *2抵消

对于S求叉击,用long long 保存, 减少精度误差

#include<cstdio>
#include<vector>
#include<cmath>
#include<string>
#include<string.h>
#include<iostream>
#include<algorithm>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
#define x  adsfadwsfasdfas
#define sx  dsafasfaseer
#define sy  dsafsfaseer
#define sx  dsafasfaser
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int MOD=1e9+7;
template <class T>
bool sf(T &ret){ //Faster Input
    char c; int sgn; T bit=0.1;
    if(c=getchar(),c==EOF) return 0;

    while(c!='-'&&c!='.'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    if(c==' '||c=='\n'){ ret*=sgn; return 1; }
    while(c=getchar(),c>='0'&&c<='9') ret+=(c-'0')*bit,bit/=10;
    ret*=sgn;
    return 1;
}
struct Point{
      ll x,y;
      Point(ll x=0.0, ll y=0.0) : x(x), y(y) {}
      Point operator-(const Point &rhs)const{
          return Point(x-rhs.x,y-rhs.y);
      }
};
typedef Point Vector;
ll cross(Vector A,Vector B){
    return A.x*B.y-A.y*B.x;
}

char s[N];
int main(void){
    int T;
    sf(T);
    int ks=0;
    while(T--){
        int n;
        sf(n);
        ll sx=0,sy=0;
        long long ans=0;
        ll on=0,in=0;
        for(int i=1;i<=n;i++){
            int x,y;
            sf(x),sf(y);
            ans+= cross({sx,sy},{sx+x,sy+y});
            sx+=x,sy+=y;
            on+=abs(__gcd(x,y));
        }
        in=(ans+2-on)/2;
        printf("Scenario #%d:\n",++ks);
        printf("%lld %lld %lld",in,on,ans/2);
        if(ans&1)   printf(".5\n\n");
        else    printf(".0\n\n");
    }

    return 0;
}