直接求凸包,输出即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath> using namespace std;
const int MAXN=100;
int n,l; int st[MAXN],stop,cnt;
int ans[MAXN]; struct point{
int x,y;
}p[MAXN]; bool cmp(point A,point B){
if(A.y<B.y) return true;
else if(A.y==B.y){
if(A.x<B.x) return true;
}
return false;
} bool multi(point a,point b,point c){
return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x)<=0;
} void slove(){
stop=0; cnt=0;
st[stop++]=0; st[stop++]=1;
for(int i=2;i<n;i++){
while(stop>1&&multi(p[st[stop-1]],p[i],p[st[stop-2]])) stop--;
st[stop++]=i;
}
for(int i=0;i<stop;i++){
ans[cnt++]=st[i];
}
stop=0;
st[stop++]=n-1; st[stop++]=n-2;
for(int i=n-3;i>=0;i--){
while(stop>1&&multi(p[st[stop-1]],p[i],p[st[stop-2]])) stop--;
st[stop++]=i;
}
for(int i=1;i<stop-1;i++)
ans[cnt++]=st[i];
} int main(){
n=0;
while(scanf("%d%d",&p[n].x,&p[n].y)!=EOF) n++;
sort(p,p+n,cmp);
slove();
int i,k;
for(k=0;k<cnt;k++){
if(p[ans[k]].x==0&&p[ans[k]].y==0) break;
}
printf("(%d,%d)\n",p[ans[k]].x,p[ans[k]].y);
for(int i=k+1;i<cnt;i++){
printf("(%d,%d)\n",p[ans[i]].x,p[ans[i]].y);
}
for(int i=0;i<k;i++){
printf("(%d,%d)\n",p[ans[i]].x,p[ans[i]].y);
}
return 0;
}

  

最新文章

  1. 增强学习(二)----- 马尔可夫决策过程MDP
  2. js实现页面跳转的几种方式
  3. 基于单决策树的AdaBoost
  4. Eclipse安装nodeclipse插件
  5. 20145236 《Java程序设计》第7周学习总结
  6. QAQ
  7. 设计模式 --&gt; (17)状态模式
  8. postman 简单教程-实现简单的接口测试
  9. hdu 5274 Dylans loves tree
  10. WPF通过DynamicResource的用法
  11. PHP学习笔记(一)
  12. 原子操作--sync/atomic的用法
  13. VMware安装MikroTik RouterOS chr
  14. Java获取配置文件跟路径
  15. Linux中断 - softirq
  16. python基础第一章
  17. C#/.NET 中推荐的 Dispose 模式的实现
  18. C# 密封(2)
  19. C++ 创建文件的方法
  20. SQL Server 2008 R2 安装时提示“Reporting Services目录数据库文件存在”

热门文章

  1. 关于form/input 的autocomplete=&quot;off&quot;属性
  2. [Apple开发者帐户帮助]三、创建证书(2)创建开发者ID证书
  3. 使用javac编译java文件
  4. xcode制作越狱后ipa安装文件
  5. Laravel5.1学习笔记10 系统架构2 应用程序结构
  6. 日期Date和String/Long之间的转换
  7. python--2、数据类型
  8. js邮箱正则表达式的使用
  9. set statistics profile on实例
  10. 释放Win8.1 WinSxS冗余更新,微软Dism来解决