首页 > 代码库 > 凸包模板***

凸包模板***

#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;}

 

凸包模板***