首页 > 其他分享 >Pick's Theorem 学习笔记

Pick's Theorem 学习笔记

时间:2024-05-04 22:23:19浏览次数:23  
标签:多边形 整点 int ll Theorem 笔记 Pick

Pick's Theorem 学习笔记

UVA10088 题目传送门

题意:顺时针或逆时针地给出一个 \(n\) 个顶点(顶点都是整点)的简单多边形,求这个多边形内部整点数量(位于多边形形上的整点不算)。

Pick's Theorem

对于一个顶点都是整点的简单多边形:

令 \(I\) 为多边形内部的整点数量,\(B\) 为多边形形上的整点数量,\(A\) 为多边形面积。有公式:

\[A = I + \dfrac B 2 - 1 \]

比较有用的是它的变形:

\[I = A - \dfrac B 2 + 1 \]

Pick's Theorem 的证明

对于一个 \(B = 3\) 的三角形,其面积 \(A\) 必然为 \(\dfrac 1 2\)。

采用数学归纳法的思路:将多边形剖成若干个 \(B=3\) 的三角形,每次切除一个三角形,要么减少一个边上的点,要么将一个内部的点转化为边上的点,直到把多边形切成一个只有两点的线段。

因此 \(A = \dfrac 1 2 (2I + B - 2) = I + \dfrac B 2 - 1\)。

Pick's Theorem from Wikipedia

关于 Pick's Theorem

皮克定理有许多有趣的应用,可以看 Matrix67 的这篇文章

相关练习:P2735 [USACO3.4] 网 Electric Fences

此题解法

利用向量叉积求出多边形面积 \(A\),用一点简单数论求出 \(B\),再用 Pick's Theorem 即可求出 \(I\)。

#include <bits/stdc++.h>
#define gcd __gcd
using namespace std;
typedef long long ll;

const int MAXN = 1000 + 5;

struct Point {
    ll x, y;
    Point(ll x, ll y) : x(x), y(y) {}
};
ll cross(Point &a, Point &b) {
    return a.x * b.y - a.y * b.x;
}

int n;
vector<Point> points;

int main() { ios::sync_with_stdio(0); cin.tie(0);
    while (1) {
        cin >> n;
        if (n == 0)
            break;
        for (int i = 1; i <= n; i++) {
            int x, y; cin >> x >> y;
            points.emplace_back(x, y);
        }
        points.push_back(points[0]);

        ll area = 0, edge = 0;
        for (int i = 1; i <= n; i++) {
            auto &a = points[i-1], &b = points[i];
            ll dx = abs(b.x - a.x), dy = abs(b.y - a.y);
            area += cross(a, b);
            edge += gcd(dx, dy);
        }

        area = abs(area) / 2;

        cout << area - edge / 2 + 1 << '\n';

        points.clear();
    }
    return 0;
}

参考

标签:多边形,整点,int,ll,Theorem,笔记,Pick
From: https://www.cnblogs.com/AugustLight/p/-/Solution-UVA10088

相关文章

  • 学习笔记:矩阵乘法
    矩阵乘法引入如果\(C=AB\),则\(c_{ij}=\sum\limits_{k=1}^{n}a_{ik}\cdotb_{kj}\),即\(A\)的第\(i\)行与\(B\)的第\(j\)列的点积。假设有\(n\)个地点,\(i\)到\(j\)做飞机有\(a_{ij}\)种选择,坐火车有\(b_{ij}\)种选择。求从\(i\)先做飞机再坐火车到......
  • QBXT五一集训DAY3笔记
    \(Day\)\(3\)位运算位运算包含了五个运算符,分别是:&与只有两个对应位都为\(1\)时才为\(1\)|或只要两个对应位中有一个\(1\)时就为\(1\)^异或只有两个对应位不同时才为\(1\)<<左移如\(n<<i\)表示将\(n\)的二进制向左移动\(i\)位,等价于\(n*2^i\)>......
  • Manacher 学习笔记
    Manacher是一个求出一个字符串中所有回文子串的利器。记录方法首先我们发现一个问题,一个长为\(S\)的字符串一共有\(S^2\)个子串,所以记录回文子串时不可能记录左右端点。如何解决呢?根据回文串的特点,我们发现,一个回文串,将它的两端各删去一个字符,那么它还是一个回文串。所以我......
  • 整体二分学习笔记
    1.简介在一些题目中,可能存在一些题目,对于每次询问直接二分可能会TLE,此时就要用到整体二分整体二分是一种离线的方法,适用于如下情况:询问答案具有可二分性修改对判定答案的贡献相互独立,修改之间互不影响效果修改如果对判定答案有贡献,则该贡献是一个确定的与判定标准无关......
  • 狂神spring学习笔记
    1.Spring1.简介一个融合器,一个简化开发的框架spring官网github地址2.Maven坐标<!--https://mvnrepository.com/artifact/org.springframework/spring-webmvc--><dependency><groupId>org.springframework</groupId><artifactId>spring-webmvc&......
  • stm32开发笔记
    GPIO全名为GeneralPurposeInputOutput,即通用输入输出。有时候简称为“IO口”。通用,说明它是常见的。输入输出,就是说既能当输入口使用,又能当输出口使用。端口,就是元器件上的一个引脚。输入模式和输出模式是GPIO的基本特性,当然GPIO还有其它模式可选。(一)模式汇总输入模式:l......
  • DSP28335学习笔记(1)
    DSP28335最小系统电源电路晶振电路作用:提供稳定的时钟晶振频率:一般为30MHz复位电路使用JTag烧录程序过程中不能复位,否则芯片可能锁死下载电路F28335启动模式存储器与寄存器F28335芯片内部的存储器包括了256K×16位的FLASH(ROM),34K×16位的SARAM,8K×16......
  • 《自动机理论、语言和计算导论》阅读笔记:p352-P401
    《自动机理论、语言和计算导论》学习第12天,p352-P401总结,总计50页。一、技术总结1.TuringMachine(TM)2.undecidability​a.Ld(thediagonalizationlanguage)3.reductionp392,Ingeneral,ifwehaveanalgorithmtoconvertinstancesofaproblemP1toi......
  • DSP28335学习笔记(2)
    实验点亮LED灯电路设计共阳极连接软件设计让F28335的GPIO68管脚输出一个低电平。使能对应IO外设时钟、配置IO功能和输出模式,上拉设置。主要程序://LED初始化函数voidLED_Init(void){EALLOW;//关闭写保护SysCtrlRegs.PCLKCR3.bit.GPIOINENCLK......
  • Python进阶篇笔记
    一、面向对象1、面向过程与面向对象面向过程:把程序流程化面向对象:把程序抽象成类,类与类之间有联系2、类与对象对象就是容器,是用来存放数据和功能的,对象就是数据和功能的集合类的作用是吧对象做区分和归类,以及解决不同对象存相同数据的问题。类也是容器,也是用来存放数据和......