博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
poj 1228 凸包
阅读量:5243 次
发布时间:2019-06-14

本文共 2371 字,大约阅读时间需要 7 分钟。

 

#include
#include
#include
#include
#include
#include
using namespace std;const double eps = 1e-8;const double PI = acos(-1.0);const double INF = 1000000000000000.000;struct Point{ double x,y; Point(double x=0, double y=0) : x(x),y(y){ } //构造函数};typedef Point Vector;Vector operator + (Vector A , Vector B){ return Vector(A.x+B.x,A.y+B.y);}Vector operator - (Vector A , Vector B){ return Vector(A.x-B.x,A.y-B.y);}Vector operator * (double p,Vector A){ return Vector(A.x*p,A.y*p);}Vector operator / (Vector A , double p){ return Vector(A.x/p,A.y/p);}bool operator < (const Point& a,const Point& b){ return a.x < b.x ||( a.x == b.x && a.y < b.y);}inline int dcmp(double x){ if(fabs(x) < eps) return 0; else return x < 0 ? -1 : 1;}bool operator == (const Point& a, const Point& b){ return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;}///向量(x,y)的极角用atan2(y,x);inline double Dot(Vector A, Vector B){ return A.x*B.x + A.y*B.y; }inline double Length(Vector A) { return sqrt(Dot(A,A)); }inline double Angle(Vector A, Vector B) { return acos(Dot(A,B) / Length(A) / Length(B)); }inline double Cross(Vector A, Vector B) { return A.x*B.y - A.y * B.x; }//凸包:/**Andrew算法思路:首先按照先x后y从小到大排序(这个地方没有采用极角逆序排序,所以要进行两次扫描),删除重复的点后得到的序列p1,p2.....,然后把p1和p2放到凸包中。从p3开始,当新的点在凸包“前进”方向的左边时继续,否则依次删除最近加入凸包的点,直到新点在左边;**///Goal[]数组模拟栈的使用;int ConvexHull(Point* P,int n,Point* Goal){ sort(P,P+n); int m = unique(P,P+n) - P; //对点进行去重; int cnt = 0; for(int i=0;i
1 && dcmp(Cross(Goal[cnt-1]-Goal[cnt-2],P[i]-Goal[cnt-2])) <= 0) cnt--; //如果希望在凸包的边上有输入点,把<= 换成 <. Goal[cnt++] = P[i]; } int temp = cnt; for(int i=m-2;i>=0;i--){ //逆序求上凸包; while(cnt>temp && dcmp(Cross(Goal[cnt-1]-Goal[cnt-2],P[i]-Goal[cnt-2])) <= 0) cnt--; Goal[cnt++] = P[i]; } if(cnt > 1) cnt--; //减一为了去掉首尾重复的; return cnt;}bool IsPointOnSegment(Point P,Point A,Point B){ return dcmp(Cross(A-P,B-P)) == 0 && dcmp(Dot(P-A,P-B)) < 0;}/*************************************分 割 线*****************************************/const int maxn = 1005;Point P[maxn];Point Goal[maxn];int main(){ freopen("E:\\acm\\input.txt","r",stdin); int T; cin>>T; while(T--){ int n; cin>>n; for(int i=0;i
n || n < 6){ printf("NO\n"); continue; } cout<
<<" "<
<<" "<
<
View Code

 

 

 

 

转载于:https://www.cnblogs.com/acmdeweilai/p/3318203.html

你可能感兴趣的文章
51nod1076 (边双连通)
查看>>
Item 9: Avoid Conversion Operators in Your APIs(Effective C#)
查看>>
学习Spring Boot:(二十八)Spring Security 权限认证
查看>>
深入浅出JavaScript(2)—ECMAScript
查看>>
STEP2——《数据分析:企业的贤内助》重点摘要笔记(六)——数据描述
查看>>
ViewPager的onPageChangeListener里面的一些方法参数:
查看>>
Jenkins关闭、重启,Jenkins服务的启动、停止方法。
查看>>
CF E2 - Array and Segments (Hard version) (线段树)
查看>>
Linux SPI总线和设备驱动架构之四:SPI数据传输的队列化
查看>>
SIGPIPE并产生一个信号处理
查看>>
CentOS
查看>>
Linux pipe函数
查看>>
java equals 小记
查看>>
爬虫-通用代码框架
查看>>
2019春 软件工程实践 助教总结
查看>>
YUV 格式的视频呈现
查看>>
Android弹出框的学习
查看>>
现代程序设计 作业1
查看>>
在android开发中添加外挂字体
查看>>
Zerver是一个C#开发的Nginx+PHP+Mysql+memcached+redis绿色集成开发环境
查看>>