博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
USACO Electric Fence
阅读量:4624 次
发布时间:2019-06-09

本文共 888 字,大约阅读时间需要 2 分钟。

  这道题就是计算三角形里面的格点的个数, 可以用匹克定理, s = n + b/2 - 1; 其中s是格点多边形的面积, n是多边形内部的格点数目, b是边界上的格点,假设有两个坐标(x1, y1) (x2, y2)  b = gcd(abs(x1-x2), (y1-y2)).代码如下:

/*    ID: m1500293    LANG: C++    PROG: fence9*/#include 
#include
#include
using namespace std;int n, m, p;struct Point{ int x, y; Point() {} Point(int x, int y):x(x), y(y) {}};int getarea(Point AB, Point AC){ return abs((AB.x*AC.y-AB.y*AC.x)/2);}int gcd(int m, int n){ if(n == 0) return m; else return gcd(n, m%n);}int main(){ freopen("fence9.in", "r", stdin); freopen("fence9.out", "w", stdout); scanf("%d%d%d", &n, &m, &p); Point AB(n, m), AC(p, 0); int SA = getarea(AB, AC); int b = gcd(n, m) + gcd(p, 0) + gcd(abs(n-p), m); int res = SA + 1 - b/2; printf("%d\n", res); return 0;}

 

转载于:https://www.cnblogs.com/xingxing1024/p/5101822.html

你可能感兴趣的文章
Spring Boot入门第一天:Hello, Spring Boot!
查看>>
使用Cocos2d-JS制作游戏新手引导(四)应用篇
查看>>
day6
查看>>
Linux: 统计代码行数和SVN修改行数的命令
查看>>
【心情】郁闷
查看>>
Java事务与JTA
查看>>
装饰器模式
查看>>
LR Socket 测试demo
查看>>
vue 路由用法
查看>>
poj2104 划分树 区间K大 在线 无修改
查看>>
java可变参数Varargs
查看>>
MySQL 5.7 安装完成后,首次登陆的几个问题
查看>>
Javascript笔记
查看>>
[禅悟人生]在每日的劳作中寻求充实与安宁
查看>>
跟锦数学2017年下半年 (不再更新网页版)
查看>>
Key/Value之王Memcached初探:三、Memcached解决Session的分布式存储场景的应用
查看>>
.NET基础拾遗(5)多线程开发基础
查看>>
Debug!Debug!Debug!
查看>>
python之subprocess模块详解--小白博客
查看>>
nmap扫描工具
查看>>