技术标签： 计算几何
pick定理：一个计算点阵中顶点在格点上的多边形面积公式，该公式可以表示为2S=2a+b-2，其中a表示多边形内部的点数，b表示多边形边界上的点数，s表示多边形的面积。
一个蛮神奇的定理。。用来求内点。。边界点作差求gcd就可以了。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inf 1e9
#define eps 1e-8
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define succ(x) (1<<x)
#define lowbit(x) (x&(-x))
#define sqr(x) ((x)*(x))
#define NM 200005
#define pi 3.141592653
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f*x;
}
struct P{
int x,y;
P(int x=0,int y=0):x(x),y(y){}
P operator-(const P&o){return P(x-o.x,y-o.y);}
P operator+(const P&o){return P(x+o.x,y+o.y);}
int operator*(const P&o){return x*o.x+y*o.y;}
int operator%(const P&o){return x*o.y-y*o.x;}
}a,b,c,d;
int s,t;
int gcd(int x,int y){return y==0?x:gcd(y,x%y);}
int main(){
while(1){
a.x=read();a.y=read();b.x=read();b.y=read();c.x=read();c.y=read();
if(!(a.x||b.x||c.x||a.y||b.y||c.y))break;
t=0;s=0;
if((b-c)*(a-c)==0)swap(a,c);
else if((a-b)*(c-b)==0)swap(b,a);
s=(b-a)%(c-a);
s=abs(s);
t=gcd(abs(b.y-a.y),abs(b.x-a.x))+gcd(abs(c.x-a.x),abs(c.y-a.y))+gcd(abs(b.x-c.x),abs(b.y-c.y));
printf("%d\n",(s-t+2)/2);
}
return 0;
}
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 6041 | Accepted: 2596 |
Description
A lattice point is an ordered pair (x, y) where x and y are both integers. Given the coordinates of the vertices of a triangle (which happen to be lattice points), you are to count the number of lattice points which lie completely inside of the triangle (points on the edges or vertices of the triangle do not count).
Input
The input test file will contain multiple test cases. Each input test case consists of six integers x1, y1, x2, y2, x3, and y3, where (x1, y1), (x2, y2), and (x3, y3) are the coordinates of vertices of the triangle. All triangles in the input will be non-degenerate (will have positive area), and −15000 ≤ x1, y1, x2, y2, x3, y3 ≤ 15000. The end-of-file is marked by a test case with x1 = y1 = x2 = y2 = x3 = y3 = 0 and should not be processed.
Output
For each input case, the program should print the number of internal lattice points on a single line.
Sample Input
0 0 1 0 0 1 0 0 5 0 0 5 0 0 0 0 0 0
Sample Output
0 6
Source
[Submit] [Go Back] [Status] [Discuss]
文章浏览阅读1.2k次。前言前一章提到，怎么搭建一个简单的web服务，咱们搭建好了，是不是需要测试下自己代码的健壮性。所以我又找了个压力测试工具。发现简go_bench单实用。正文 安装方式一：go get github.com/linkxzhou/http_bench方式二：git clone [email protected]:linkxzhou/http_bench.git下载..._go bench
文章浏览阅读888次。先在项目设置的Physics中设置在内容浏览器增加物理材质在里面进行定义进入人物的physics中将自己创的定义进去这样角色就拥有了物理材质，接下来进入程序加上互动。呈现点效果进入项目.h文件中增加宏定义，=//就是给这两个物理材质增加个假名，等下容易进行调用#define SURFACE_FLESHDEFAULT SurfaceType1#define SU..._c2039"surfacetype": 不是 "tweakobjectptr
文章浏览阅读569次。话不多说,直接进入正题.首先,要在微信公众平台注册一个公众账号,我这边是用的测试账号.有了账号之后进入微信公众平台获取appID和appsecret以供调用接口.微信开发者文档地址:https://developers.weixin.qq.com/doc/offiaccount/OA_Web_Apps/Wechat_webpage_authorization.html首先判断coo..._java vue 微信公众号openid自动登录
文章浏览阅读1.7k次。问题描述：mysql执行还有自定义参数的sql语句会报错“Fatal error encountered during command execution”（执行命令时遇到的致命错误）问题原因：发帖的时候刚用msql不久，公司项目里遇见的，好像是mysql执行非过程语句步能使用变量吧，有清楚的朋友可以评论补充一下解决方法：数据库连接字符出添加”Allow User Variables=T..._fatal error encountered during command execution. csdn
文章浏览阅读3.2k次。工业互联网涉及很多领域：物联网、IoT、5G、数字孪生、边缘计算、工业4.0、智能制造等概念。其中，工业生产可视化将成为新一轮制造革命的核心竞争力。工业企业中生产线处于高速运转，由工业设备所产生、采集和处理的数据量远大于企业中计算机和人工产生的数据，生产线的高速运转则对数据的实时性要求也更高。破解这些大数据就是企业在新一轮制造革命中赢得竞争力的钥匙。因此，工业生产可视化系统是工业制造业的最佳选..._wed组态图片
文章浏览阅读2.6k次。问题：cocos热更新成功但是没变化？热更新资源未生效？在Cocos Creator v2.3.1中，使用扩展商店里的热更新工具实现热更新，热更新完毕后自动重启游戏，此时更新可以成功，但是重启游戏后热更新的效果无效了！但是版本却是最新的！_cocos热更新成功后还是旧的
文章浏览阅读809次。收稿日期: 2012 年 3 月 基于 MATLAB 的机床主轴结构优化设计 刘红娟宝鸡文理学院 摘要: 介绍了机床主轴的结构，建立了以质量最轻为目标函数的优化模型，运用 MATLAB 优化工具箱中的fmincon 函数对其进行优化设计。通过对已有的机床主轴实例进行优化求解和分析，对比优化前后的数据信息，表明优化之后的机床主轴质量更轻，且编程简单，设计效率高。最后绘出了实例的各设计变量和目标函数之..._机床主轴优化设计matlab程序
文章浏览阅读3.5k次，点赞3次，收藏10次。转载至https://www.cnblogs.com/dmtz/p/11091090.htmlfrom openpyxl import *class excel(): def __init__(self,file): self.file = file self.wb = load_workbook(self.file) sheets = self.wb.get_sheet_names() self.sheet = sheets_python get excel表的行与列值
文章浏览阅读4.5w次，点赞14次，收藏147次。处理代码分为两部分，第一部分用于去除边缘的突出部，第二部分用于边缘光滑。具体如下所示1.去除边缘突出部//去除二值图像边缘的突出部//uthreshold、vthreshold分别表示突出部的宽度阈值和高度阈值//type代表突出部的颜色，0表示黑色，1代表白色 void delete_jut(Mat& src, Mat& dst, int uthreshold, int vthre_opencv 凸出明显的地方删除
文章浏览阅读1.1k次。BEGINJava面试题全集84集系列：https://www.bilibili.com/video/av29503459?from=search&seid=6567704966922691267Java高频面试题-尚硅谷-Java面试题第一季：https://www.bilibili.com/video/av37602130?from=search&se..._$module_dir$ application.properties
文章浏览阅读1w次，点赞11次，收藏114次。1. 要求对灰度图像进行离散傅里叶变换（Discrete Fourier Transfom, DFT）变换，在频域上分别使用理想的高通和低通滤波器进行滤波，显示滤波后的频域图像，以及逆离散傅里叶变换（Inverse Discrete Fourier Transfom, IDFT）变换后的空域图像，观察振铃现象。2. 读取灰度图像这里读取matlab自带的“摄影师”灰度图像%% 读取图像x = imread('cameraman.tif');figure, imshow(x), titl_灰度图像频域处理
文章浏览阅读1.3k次，点赞36次，收藏23次。安全用电监测预警系统通过物联网技术对电气引发火灾的主要因素（导线温度、电流、电压和漏电流）进行不间断的数据跟踪与统计分析，实时发现电气线路和用电设备存在的安全隐患（如：线缆温度异常、短路、过载、过压、欠压及漏电等），有效防止电气火灾的发生。