POJ 2007
2024-09-02 07:53:17
直接求凸包,输出即可。
#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;
}
最新文章
- 增强学习(二)----- 马尔可夫决策过程MDP
- js实现页面跳转的几种方式
- 基于单决策树的AdaBoost
- Eclipse安装nodeclipse插件
- 20145236 《Java程序设计》第7周学习总结
- QAQ
- 设计模式 -->; (17)状态模式
- postman 简单教程-实现简单的接口测试
- hdu 5274 Dylans loves tree
- WPF通过DynamicResource的用法
- PHP学习笔记(一)
- 原子操作--sync/atomic的用法
- VMware安装MikroTik RouterOS chr
- Java获取配置文件跟路径
- Linux中断 - softirq
- python基础第一章
- C#/.NET 中推荐的 Dispose 模式的实现
- C# 密封(2)
- C++ 创建文件的方法
- SQL Server 2008 R2 安装时提示“Reporting Services目录数据库文件存在”
热门文章
- 关于form/input 的autocomplete=";off";属性
- [Apple开发者帐户帮助]三、创建证书(2)创建开发者ID证书
- 使用javac编译java文件
- xcode制作越狱后ipa安装文件
- Laravel5.1学习笔记10 系统架构2 应用程序结构
- 日期Date和String/Long之间的转换
- python--2、数据类型
- js邮箱正则表达式的使用
- set statistics profile on实例
- 释放Win8.1 WinSxS冗余更新,微软Dism来解决