HDU_6590 Code 【凸包】

一、题目

　　Code
二、分析

　　题目描述了一大堆东西，就是想问二维空间里，能不能确定$d w_1 w_2$使得函数满足$f(x_1,x_2) = y$，并且$sign(x)$函数是一个信号函数，只取3种值。
　　那么将函数拆开其实就是$d + w_{1}x_{i_1} + w_{2}x_{i_2} = y$，因为$y$给定，发现就是一个二维平面里的直线，我们只需要将所有$y=1$和$y=-1$的点分类，能不能确定$w_1$和$w_2$使得所有点的值都等于$-1$或者$1$，即$<0$或者$>0$而等于$0$的情况相当于就是一条直线，将两类点分开。所以转换一下就是求两个凸包是否相交。
三、AC代码

  1 #include <bits/stdc++.h>

  2

  3 using namespace std;

  4 #define ll long long

  5 #define Min(a,b) ((a)>(b)?(b):(a))

  6 #define Max(a,b) ((a)>(b)?(a):(b))

  7 #define P pair<int, int>

  8 const double EPS = 1e-8;

  9 const int MAXN = 1e2+13;

 10 const int INF = 1e5;

 11

 12 //带误差比较，返回x是否等于y

 13 inline bool dcmp(double x, double y = 0)

 14 {

 15     return fabs(x - y) <= EPS;

 16 }

 17

 18 //向量

 19 //需要使用一个原点到(x,y)的有向线段表示

 20 typedef struct Vec

 21 {

 22     double x, y;

 23

 24     Vec(double x = 0, double y = 0) : x(x),y(y) {}

 25

 26     //向量相加

 27     Vec operator+(const Vec &v) const{

 28         return Vec(x + v.x, y + v.y);

 29     }

 30

 31     //向量相减

 32     Vec operator-(const Vec &v) const{

 33         return Vec(x - v.x, y - v.y);

 34     }

 35

 36     //向量数乘 即向量*数d

 37     Vec operator*(double d) const{

 38         return Vec(x * d, y * d);

 39     }

 40

 41     Vec operator/(double d) const{

 42         return Vec(x / d, y / d);

 43     }

 44

 45     //范数，及长度的平方

 46     double norm() const{

 47         return x * x + y * y;

 48     }

 49 }Pt;

 50

 51 //点乘

 52 double dot(const Vec &a, const Vec &b)

 53 {

 54     return a.x * b.x + a.y * b.y;

 55 }

 56

 57 //叉乘

 58 //叉乘可以表示四边形的面积

 59 double cross(const Vec &a, const Vec &b)

 60 {

 61     return a.x * b.y - a.y * b.x;

 62 }

 63

 64 //线段，两个点表示

 65 struct Seg

 66 {

 67     Pt a, b;

 68

 69     Seg(const Pt &a, const Pt &b) : a(a), b(b) {}

 70

 71     //线段包含点(点在线段上)

 72     //先判断是否叉乘等于 0， 如果等于0表示点在线段所在的直线上

 73     //再判断点乘是否小于等于0

 74     //小于0表示两向量夹角为180，刚好在线段内，

 75     //等于0表示刚好在线段两端

 76     bool include(const Pt &p) {

 77         return dcmp(cross(a - p, b - p)) && dot(a - p, b - p) <= 0;

 78     }

 79 };

 80

 81 //直线，两个点表示

 82 struct Line

 83 {

 84     Pt a, b;

 85

 86     Line() {}   //提供一个不需要参数的构造函数

 87     Line(const Pt &a, Pt &b) : a(a), b(b) {}

 88

 89     //点在直线上

 90     bool include(const Pt &p) const {

 91         return dcmp(cross(a - p, b - p));

 92     }

 93

 94     //两直线关系

 95     //  1 表示两直线相交（1交点）

 96     //  0 表示两直线平行（0交点）

 97     // -1 表示两直线重合（无数交点）

 98     static int relation(const Line &a, const Line &b) {

 99         if(a.include(b.a) && a.include(b.b))    return -1;

100         else if(dcmp(cross(a.b - a.a, b.b - b.a)))  return 0;

101         else return 1;

102     }

103

104     //求两直线交点(若有一个交点)

105     static Pt intersect(const Line &a, const Line &b) {

106         double s1 = cross(b.a - a.a, b.b - a.a), s2 = cross(b.b - a.b, b.a - a.b);

107         return a.a + (a.b - a.a) * s1 / (s1 + s2);

108     }

109

110 };

111

112 //凸包的交点

113 int n;

114 Pt a[MAXN + 1];

115

116 //凸包极角比较函数

117 inline bool compare(const Pt &a, const Pt &b)

118 {

119     //以第一个点为原点的两个向量

120     Vec va = a - ::a[1], vb = b - ::a[1];

121     double t = cross(va, vb);

122     //t>0 表示b的极角大，b在a的逆时针方向

123     //t<0 表示a的极角大，b在a的顺时针方向

124     //t=0 表示a与b极角相同，则比较长度

125     if(!dcmp(t)) return t > 0;

126     else return va.norm() < vb.norm();

127 }

128

129 //多边形

130 struct Poly

131 {

132     std::vector<Pt> pts;

133

134     //判断点是否在多边形内

135     //射线法，作平行于x轴的线

136     bool include(const Pt &p) const {

137         int cnt = 0;

138         //判断与每条边是否有交点

139         for(size_t i = 0; i < pts.size(); i++) {

140             //枚举相邻两点

141             const Pt &a = pts[i], &b = pts[(i+1)%pts.size()];

142

143             //如果点p在边AB上

144             if(Seg(a, b).include(p))    return true;

145

146             double d1 = a.y - p.y, d2 = b.y - p.y, tmp = cross(a - p, b- p);

147             //如果tmp >= 0 && d1 >= 0 && d2 <= 0 那么点在多边形内会被标记两次

148             //将无法排除点在外面刚好记录两次的情况

149             if( (tmp >= 0 && d1 >= 0 && d2 < 0) || (tmp <= 0 && d1 < 0 && d2 >=0)) cnt++;

150         }

151         //因为点可能刚好在外面与边交于一顶点，那么会判断两次

152         //所以根据判断的次数是否为奇数判断

153         return cnt % 2 == 1;

154     }

155

156     //多边形面积

157

158     bool area() const {

159         double res = 0;

160         for(size_t i = 0; i < pts.size(); i++) {

161             //枚举两个点

162             const Pt &a = pts[i], &b = pts[(i+1) % pts.size()];

163             res += cross(a, b);

164         }

165         return res/2;

166     }

167

168     //求凸包，结果存储在自身pts中

169     void convex() {

170         int id = 1;

171         //找最左下角的点当原点

172         for(int i = 1; i <= n; i++) {

173             if(a[i].x < a[id].x || (a[i].x == a[id].x && a[i].y < a[id].y))

174                 id = i;

175         }

176         if(id != 1) std::swap(a[1], a[id]);

177

178         //极角排序

179         std::sort(a + 2, a + n + 1, &compare);

180

181         //扫描

182         pts.push_back(a[1]);

183         for(int i = 2; i <= n; i++) {

184             //比较，如果最后一个点在凸包内，则被弹出

185             while(pts.size() >= 2 && cross(a[i] - pts[pts.size() - 2], pts.back() - pts[pts.size() - 2]) >= 0 )

186                 pts.pop_back();

187             pts.push_back(a[i]);

188         }

189     }

190 };

191

192 bool solve(Poly &a, Poly &b)

193 {

194     for(int i = 0; i < b.pts.size(); i++) {

195         if(a.include(b.pts[i]))

196             return false;

197     }

198     for(int i = 0; i < a.pts.size(); i++) {

199         if(b.include(a.pts[i]))

200             return false;

201     }

202     return true;

203 }

204

205 Pt c1[MAXN], c2[MAXN];

206

207 int main()

208 {

209     freopen("input.txt", "r", stdin);

210     // freopen("out.txt", "w", stdout);

211     int T;

212     scanf("%d", &T);

213     while(T--) {

214         int N, x, y, f;

215         scanf("%d", &N);

216         Poly p1, p2;

217         int N1 = 1, N2 = 1;

218         for(int i = 0; i < N; i++) {

219             scanf("%d%d%d", &x, &y, &f);

220             if(f == -1) {

221                 c1[N1++] = Pt(x+INF, y+INF);

222             }

223             else {

224                 c2[N2++] = Pt(x+INF, y+INF);

225             }

226         }

227         for(int i = 1; i < N1; i++) {

228             a[i] = c1[i];

229         }

230         n = N1 - 1;

231         p1.convex();

232         for(int i = 1; i < N2; i++) {

233             a[i] = c2[i];

234         }

235         n = N2 - 1;

236         p2.convex();

237         // cout << " py1    " << endl;

238         // for(int i = 0; i< p1.pts.size(); i++) {

239         //     cout << p1.pts[i].x << " , " << p1.pts[i].y << endl;

240         // }

241         // cout << " py2    " << endl;

242         // for(int i = 0; i< p2.pts.size(); i++) {

243         //     cout << p2.pts[i].x << " , " << p2.pts[i].y << endl;

244         // }

245         if(solve(p1, p2)) {

246             puts("Successful!");

247         }

248         else puts("Infinite loop!");

249     }

250     return 0;

251 }
巴特西

HDU_6590 Code 【凸包】

一、题目

二、分析

三、AC代码

最新文章

热门文章
