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;
}


目录
相关文章
|
机器学习/深度学习
HDU2376——Average distance(思维+树形DP)
HDU2376——Average distance(思维+树形DP)
91 0
|
机器学习/深度学习
HDOJ(HDU) 2524 矩形A + B(推导公式、)
HDOJ(HDU) 2524 矩形A + B(推导公式、)
98 0
HDOJ(HDU) 2524 矩形A + B(推导公式、)
HDOJ 2076 夹角有多大(题目已修改,注意读题)
HDOJ 2076 夹角有多大(题目已修改,注意读题)
100 0
HDOJ(HDU) 2156 分数矩阵(嗯、求和)
HDOJ(HDU) 2156 分数矩阵(嗯、求和)
104 0
HDOJ/HDU 2566 统计硬币(公式~遍历~)
HDOJ/HDU 2566 统计硬币(公式~遍历~)
145 0
HDOJ(HDU) 2138 How many prime numbers(素数-快速筛选没用上、)
HDOJ(HDU) 2138 How many prime numbers(素数-快速筛选没用上、)
99 0
HDOJ(HDU) 2504 又见GCD(利用最大公约数反推)
HDOJ(HDU) 2504 又见GCD(利用最大公约数反推)
106 0
|
机器学习/深度学习
HDOJ(HDU) 2083 简易版之最短距离(中位数)
HDOJ(HDU) 2083 简易版之最短距离(中位数)
136 0