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$的情况相当于就是一条直线，将两类点分开。所以转换一下就是求两个凸包是否相交。

1 #include
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
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 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 }