若是凉夜已成梦

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


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1222: Convex Hull

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

题目描述

Finding the convex hull of a set of points is an important problem that is often part of a larger problem. There are many algorithms for finding the convex hull. Since problems involving the convex hull sometimes appear in the ACM World Finals, it is a good idea for contestants to know some of these algorithms.
Finding the convex hull of a set of points in the plane can be divided into two sub-tasks. First, given a set of points, find a subset of those points that, when joined with line segments, form a convex polygon that encloses all of the original points. Second, output the points of the convex hull in order, walking counter-clockwise around the polygon. In this problem, the first sub-task has already been done for you, and your program should complete the second sub-task. That is, given the points that are known to lie on the convex hull, output them in order walking counter-clockwise around the hull.

输入

The first line of input contains a single integer 3 <= n <= 100000, the number of points. The following n lines of input each describe a point. Each of these lines contains two integers and either a Y or an N, separated by spaces. The two integers specify the x- and y-coordinates of the point. A Y indicates that the point is on the convex hull of all the points, and a N indicates that it is not. The x- and y-coordinates of each point will be no less than -1000000000 and no greater than 1000000000. No point will appear more than once in the input. The points in the input will never all lie on a line.

输出

First, output a line containing a single integer m, the number of points on the convex hull. Next output m lines, each describing a point on the convex hull, in counter-clockwise order around the hull. Each of these lines should contain the x-coordinate of the point, followed by a space, followed by the y-coordinate of the point. Start with the point on the hull whose x-coordinate is minimal. If there are multiple such points, start with the one whose y-coordinate is minimal.

样例输入

5
1 1 Y
1 -1 Y
0 0 N
-1 -1 Y
-1 1 Y

样例输出

4
-1 -1
1 -1
1 1
-1 1

参考代码

暂无

解析

暂无

hustoj

发表评论 取消回复

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

*
*


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

若是凉夜已成梦

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

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

友情链接

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