Codeforces 166B. Polygons（凸包）

题意：

解法：

解法1:
计算A的凸包，再计算A+B的混合凸包，
如果两个凸包的点相同则表示B在A内。

解法2:
记录每个点是A的还是B的，然后计算A+B的混合凸包，
判断凸包中有没有B的点即可。
1
2
3
4
5
6
7

Code1：

计算A的凸包，再计算A+B的混合凸包，
如果两个凸包的点相同则表示B在A内。

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define int long long
#define PI pair<int, int>
const int maxm = 2e5 + 5;

// 依赖的计算几何模板
inline int dcmp(double x){
  constexpr double eps=1e-8;
  if (x<-eps)return -1;
  if (x>eps)return 1;
  return 0;
}
struct Point {
  double x,y;
  Point()=default;
  Point(double x,double y):x(x),y(y){}
  Point operator+(const Point& p){
    return Point(x+p.x,y+p.y);
  }
  Point operator-(const Point& p){
    return Point(x-p.x,y-p.y);
  }
  // dot mul.
  Point operator*(double k){
    return Point(x*k,y*k);
  }
  // cross mul.
  double operator*(const Point& p){
    return x*p.y-y*p.x;
  }
  double dist(const Point& p){
    const Point dp=*this-p;
    return sqrt(dp.x*dp.x+dp.y*dp.y);
  }
};
// Andrew算法
struct AndrewConvexHull {
  // some define.
  static const int N = 2e5+5;
  int stk[N],tp;
  bool used[N];
  void cal(Point* p, int n) {
    // init
    tp=0;
    for(int i=1;i<=n;i++)used[i]=0;
    //
    sort(p+1,p+1+n,[](const Point& a,const Point& b) {
      if (a.x!=b.x)return a.x<b.x;
      return a.y<b.y;
    });
    // 点1不标记为used
    // 等到计算上凸壳的时候会被自动标记上
    stk[++tp]=1;
    for(int i=2;i<=n;i++){
      // dcmp<0会保留共线的点
      // 如果改成dcmp<=0则不会保留共线的点
      while(tp>1&&dcmp((p[stk[tp]]-p[stk[tp-1]])*(p[i]-p[stk[tp-1]]))<0) {
        used[stk[tp]]=0;
        tp--;
      }
      used[i]=1;
      stk[++tp]=i;
    }
    int ltp=tp;
    for(int i=n-1;i>=1;i--){
      if(used[i])continue;
      while(tp>ltp&&dcmp((p[stk[tp]]-p[stk[tp-1]])*(p[i]-p[stk[tp-1]]))<0) {
        used[stk[tp]]=0;
        tp--;
      }
      used[i]=1;
      stk[++tp]=i;
    }
    // stk[1]=stk[tp]=1，这里去掉一个重复的p[1]
    if(tp>1)tp--;
  }
}T;
int n,m;
Point a[maxm];
Point b[maxm];
void solve(){
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>a[i].x>>a[i].y;
  }
  cin>>m;
  for(int i=1;i<=m;i++){
    cin>>b[i].x>>b[i].y;
  }
  // 计算a的凸包
  T.cal(a,n);
  vector<Point> CA;
  for(int i=1;i<=T.tp;i++){
    CA.push_back(a[T.stk[i]]);
  }
  // 计算a和b的混合凸包
  for(int i=1;i<=m;i++){
    a[i+n]=b[i];
  }
  T.cal(a,n+m);
  vector<Point> CAB;
  for(int i=1;i<=T.tp;i++){
    CAB.push_back(a[T.stk[i]]);
  }
  int ok=1;
  if(CA.size()!=CAB.size()){
    ok=0;
  } else {
    for(int i=0;i<(int)CA.size();i++){
      if(dcmp(CA[i].x-CAB[i].x)!=0 || dcmp(CA[i].y-CAB[i].y)!=0){
        ok=0;break;
      }
    }
  }
  if(ok)cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
}
signed main() {
// #define MULTI_CASE
  ios::sync_with_stdio(0);
  cin.tie(0);
#ifndef ONLINE_JUDGE
  freopen("../in.txt", "r", stdin);
  freopen("../out.txt", "w", stdout);
#endif
#ifdef MULTI_CASE
  int T;
  cin >> T;
  while (T--)
#endif
    solve();
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

Code2：

记录每个点是A的还是B的，然后计算A+B的混合凸包，
判断凸包中有没有B的点即可。

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define int long long
#define PI pair<int, int>
const int maxm = 2e5 + 5;

// 依赖的计算几何模板
inline int dcmp(double x){
  constexpr double eps=1e-8;
  if (x<-eps)return -1;
  if (x>eps)return 1;
  return 0;
}
struct Point {
  double x,y;
  int op;
  Point()=default;
  Point(double x,double y):x(x),y(y){}
  Point operator+(const Point& p){
    return Point(x+p.x,y+p.y);
  }
  Point operator-(const Point& p){
    return Point(x-p.x,y-p.y);
  }
  // dot mul.
  Point operator*(double k){
    return Point(x*k,y*k);
  }
  // cross mul.
  double operator*(const Point& p){
    return x*p.y-y*p.x;
  }
  double dist(const Point& p){
    const Point dp=*this-p;
    return sqrt(dp.x*dp.x+dp.y*dp.y);
  }
};
// Andrew算法
struct AndrewConvexHull {
  // some define.
  static const int N = 2e5+5;
  int stk[N],tp;
  bool used[N];
  void cal(Point* p, int n) {
    // init
    tp=0;
    for(int i=1;i<=n;i++)used[i]=0;
    //
    sort(p+1,p+1+n,[](const Point& a,const Point& b) {
      if (a.x!=b.x)return a.x<b.x;
      return a.y<b.y;
    });
    // 点1不标记为used
    // 等到计算上凸壳的时候会被自动标记上
    stk[++tp]=1;
    for(int i=2;i<=n;i++){
      // dcmp<0会保留共线的点
      // 如果改成dcmp<=0则不会保留共线的点
      while(tp>1&&dcmp((p[stk[tp]]-p[stk[tp-1]])*(p[i]-p[stk[tp-1]]))<0) {
        used[stk[tp]]=0;
        tp--;
      }
      used[i]=1;
      stk[++tp]=i;
    }
    int ltp=tp;
    for(int i=n-1;i>=1;i--){
      if(used[i])continue;
      while(tp>ltp&&dcmp((p[stk[tp]]-p[stk[tp-1]])*(p[i]-p[stk[tp-1]]))<0) {
        used[stk[tp]]=0;
        tp--;
      }
      used[i]=1;
      stk[++tp]=i;
    }
    // stk[1]=stk[tp]=1，这里去掉一个重复的p[1]
    if(tp>1)tp--;
  }
}T;
int n,m;
Point a[maxm];
void solve(){
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>a[i].x>>a[i].y;
    a[i].op=1;
  }
  cin>>m;
  for(int i=1;i<=m;i++){
    cin>>a[i+n].x>>a[i+n].y;
    a[i+n].op=2;
  }
  // 计算a和b的混合凸包
  T.cal(a,n+m);
  int ok=1;
  for(int i=1;i<=T.tp;i++){
    if(a[T.stk[i]].op==2){
      ok=0;break;
    }
  }
  if(ok)cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
}
signed main() {
// #define MULTI_CASE
  ios::sync_with_stdio(0);
  cin.tie(0);
#ifndef ONLINE_JUDGE
  freopen("../in.txt", "r", stdin);
  freopen("../out.txt", "w", stdout);
#endif
#ifdef MULTI_CASE
  int T;
  cin >> T;
  while (T--)
#endif
    solve();
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

---