若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1604: Trees on My Island

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,222

题目描述

I have bought an island where I want to plant trees in rows and columns. The trees will be planted to form a rectangular grid, so each can be thought of as having integer coordinates by taking a suitable grid point as the origin.

A sample of my island
However, my island is not rectangular. I have identified a simple polygonal area inside the island with vertices on the grid points and have decided to plant trees on grid points lying strictly inside the polygon.

I seek your help in calculating the number of trees that can be planted.

输入

The input file may contain multiple test cases. Each test case begins with a line containing an integer N ( 3<=N<=1, 000) identifying the number of vertices of the polygon. The next N lines contain the vertices of the polygon in either the clockwise or counterclockwise direction. Each of these N lines contains two integers identifying the x- and y-coordinates of a vertex. You may assume that the absolute value of all coordinates will be no larger than 1,000,000.
A test case containing a zero for N in the first line terminates the input.

输出

For each test case, print a line containing the number of trees that can be planted inside the polygon.

样例输入

12
3 1
6 3
9 2
8 4
9 6
9 9
8 9
6 5
5 8
4 4
3 5
1 3
12
1000 1000
2000 1000
4000 2000
6000 1000
8000 3000
8000 8000
7000 8000
5000 4000
4000 5000
3000 4000
3000 5000
1000 3000
0


样例输出

21
25990001


参考代码

暂无

解析

暂无

hustoj

发表评论 取消回复

电子邮件地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

Dreams孤独患者 原站点 Skip
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist