首页 > 代码库 > 凸包模板***
凸包模板***
#include <cstdio>#include <cstring>#include <vector>#include <algorithm>#include <iostream>#include <map>#include <queue>#include <stack>#include <cmath>//#pragma comment(linker, "/STACK:102400000,102400000")using namespace std;#define PF(x) cout << "debug: " << x << " ";#define EL cout << endl;#define PC(x) puts(x);typedef long long ll;#define CLR(x, v) sizeof (x, v, sizeof(x))using namespace std;const int INF = 0x5f5f5f5f;const int maxn = 4e5 + 10;const int mod = 1e9 + 7;const double eps = 1e-8;const double PI = acos(-1);int sgn(double x){ if(abs(x) < eps) return 0; if(x < 0) return -1; else return 1;}struct Point{ double x,y; Point(){} Point(double _x,double _y) { x=_x;y=_y; } Point operator - (const Point &b) const { return Point(x-b.x,y-b.y); } bool operator < (const Point &b) const { return (x<b.x)||(x==b.x&&y<b.y); }};//*两点间距离int n,m;Point p[maxn],pb[maxn],res[maxn];double dist(Point a,Point b){ return sqrt(1.0*(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}//相对于p[0]的极角排序int cmp(Point a,Point b){ if(a.x==b.x)return a.y<b.y; return a.x<b.x;}double cross(Point a,Point b){ return a.x*b.y-b.x*a.y;}int andrew(int n)//从左下开始逆时针凸包,res中存的既是按顺序的凸包点,返回的是0~m-1共m个点{ sort(p,p+n); int m=0; for (int i=0;i<n;i++) { while (m>1&&cross(res[m-1]-res[m-2],p[i]-res[m-2])<0) --m; res[m++]=p[i]; } int k=m; for (int i=n-2;i>=0;--i) { while (m>k&&cross(res[m-1]-res[m-2],p[i]-res[m-2])<0) --m; res[m++]=p[i]; } if (m>1) --m; return m;}int main(){ //freopen("in.txt","r",stdin); cin>>n; for(int i = 0;i < n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); cin>>m; for(int i = 0;i < m;i++){ scanf("%lf%lf",&p[i+n].x,&p[i+n].y); pb[i] = p[i+n]; } int num = andrew(n+m); // cout<<num<<endl; int fg = 0; sort(pb,pb+m); for(int i = 0;i < num;i++){ // cout<<res[i].x<<" "<<res[i].y<<endl; int tmp = lower_bound(pb,pb+m,res[i]) - pb; if(sgn(dist(res[i],pb[tmp])) == 0){ fg = 1; // break; } } if(fg) cout<<"NO"<<endl; else cout<<"YES"<<endl; return 0;}
凸包模板***
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。