Space Ant
Space Ant
- It can not turn right due to its special body structure.
- It leaves a red path while walking.
- It hates to pass over a previously red colored path, and never does that.
The pictures transmitted by the Discovery space ship depicts that plants in the Y1999 grow in special points on the planet. Analysis of several thousands of the pictures have resulted in discovering a magic coordinate system governing the grow points of the plants. In this coordinate system with x and y axes, no two plants share the same x or y.
An M11 needs to eat exactly one plant in each day to stay alive. When it eats one plant, it remains there for the rest of the day with no move. Next day, it looks for another plant to go there and eat it. If it can not reach any other plant it dies by the end of the day. Notice that it can reach a plant in any distance.
The problem is to find a path for an M11 to let it live longest.
Input is a set of (x, y) coordinates of plants. Suppose A with the coordinates (xA, yA) is the plant with the least y-coordinate. M11 starts from point (0,yA) heading towards plant A. Notice that the solution path should not cross itself and all of the turns should be counter-clockwise. Also note that the solution may visit more than two plants located on a same straight line.
Input
Output
Sample Input
2 10 1 4 5 2 9 8 3 5 9 4 1 7 5 3 2 6 6 3 7 10 10 8 8 1 9 2 4 10 7 6 14 1 6 11 2 11 9 3 8 7 4 12 8 5 9 20 6 3 2 7 1 6 8 2 13 9 15 1 10 14 17 11 13 19 12 5 18 13 7 3 14 10 16
Sample Output
10 8 7 3 4 9 5 6 2 1 10 14 9 10 11 5 12 8 7 6 13 4 14 1 3 2
题目大意就是,在二维平面是找出一条路径,满足:
1.只能向左弯折;
2.弯折的地方只能是给定的点集中的点;
3.路径不能与之前的有相交;
4.要求经过给定的点越多越好.
这一题用到的是凸包的思想,却不是凸包.先说结论:我们每次以前一次到达的点为最下方的点(同时为基准点),旋转这个图,下一个到达的点就是新图中最最右边,且距离x轴最近的点(先满足前一个要求).
那么这个其实就是运用到凸包的排序思想,对于上述的条件,其实只需要运用叉积做cmp来排序就好啦.由于n很小,所以这题就能稳稳地过了.
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<iostream> #include<stack> using namespace std; int n,nowpos; ]; point operator - (point u,point v){point ret; ret.x=u.x-v.x,ret.y=u.y-v.y; return ret;} int dis(point u,point v){return (u.x-v.x)*(u.x-v.x)+(u.y-v.y)*(u.y-v.y);} int cross(point u,point v){return u.x*v.y-v.x*u.y;} inline int read(){ ,f=; char ch=getchar(); '){if (ch=='-') f=-f; ch=getchar();} +ch-',ch=getchar(); return x*f; } bool cmp(const point &P,const point &Q){ ||cross(P-a[nowpos],Q-a[nowpos])==&&dis(a[nowpos],P)<dis(a[nowpos],Q); } int main(){ for (int T=read(); T; T--){ n=read(),memset(a,,sizeof a); ; i<=n; i++) a[i].index=read(),a[i].x=read(),a[i].y=read(); ; i<=n; i++) ].y||a[i].y==a[].y&&a[i].x<a[].x) swap(a[],a[i]); nowpos=; ; i<=n; i++){ sort(a+i,a+n+,cmp); nowpos++; } printf("%d",n); ; i<=n; i++) printf(" %d",a[i].index); puts(""); } ; }
最新文章
- [Java 缓存] Java Cache之 DCache的简单应用.
- S2---深入.NET平台和C#编程的完美总结
- LightOJ1171 Knights in Chessboard (II)(二分图最大点独立集)
- AJAX04 JQ的AJAX
- ssh 免密码登录
- POJ 1754 Splay
- hello world of hibernate Annotation
- [BZOJ 1692] [Usaco2007 Dec] 队列变换 【后缀数组 + 贪心】
- Web Components
- [LeetCode] Non-negative Integers without Consecutive Ones 非负整数不包括连续的1
- 基于线程池的多线程售票demo2.0(原创)
- Android OpenGL ES 开发(五): OpenGL ES 使用投影和相机视图
- (8)Microsoft office Word 2013版本操作入门_制作传单海报
- [Spark] Spark 安装配置
- java自定义注解学习(一)_demo小练习
- UWP 自然灾害App在刷新数据后卡死的解决方案
- 如何杀掉Monkey测试
- Linux中配置ftp服务器
- Win10 怎么给php文件设置默认打开应用
- 08_zookeeper的客户端工具curator_watcher
热门文章
- java多线程同步机制
- Java问题解决:Java compiler level does not match the version of the installed Java project facet.
- Codeforces 776D The Door Problem
- C# Combobox联动
- ERROR: child process failed, exited with error number 100
- C# 使用 protobuf 进行对象序列化与反序列化
- SQL中 根据行号设置每行数据的排序数值
- less 前端css利器 工程化、逻辑化 css 文件
- Java代理机制之初见(理解及实现)
- 第 5 章 网络 - 031 - none和host网络的适用场景