链接: http://acm.hdu.edu.cn/showproblem.php?pid=6590 题面: After returning with honour from ICPC(International Cat Programming Contest) World Finals, Tom decides to say goodbye to ICPC and start a new period of life. He quickly gets interested in AI.
In the subject of Machine Learning, there is a classical classification model called perceptron, defined as follows:
Assuming we get a set of training samples: D={(x1,y1),(x2,y2),…,(xN,yN)}, with their inputs x∈Rd, and outputs y∈{−1,1}. We will try to find a function f(x)=sign(∑di=1wi⋅xi+b)=sign(wT⋅x+b) so that f(xi)=yi,i=1,2,…,N.
w,x mentioned above are all d-dimensional vectors, i.e. w=(w1,w2,…,wd), x=(x1,x2,…,xd). To simplify the question, let w0=b, x0=1, then f(x)=sign(∑di=0wi⋅xi)=sign(wT⋅x). Therefore, finding a satisfying function f(x) is equivalent to finding a proper w.
To solve the problem, we have a algorithm, PLA(Popcorn Label Algorithm).
Accoding to PLA, we will randomly generate w.
If f(x)=sign(wT⋅x) fails to give any element (xi,yi)∈D the right classification, i.e. f(xi)≠yi, then we will replace w with another random vector. We will do this repeatedly until all the samples ∈D are correctly classified.
As a former-JBer, Tom excels in programming and quickly wrote the pseudocode of PLA.
w := a random vector while true do flag:=true for i:=1 to N do if f(x[ i ]) != y[ i ] then flag:=false break if flag then break else w := a random vector return w
But Tom found that, in some occasions, PLA will end up into an infinite loop, which confuses him a lot. You are required to help Tom determine, when performed on a given sample set D, if PLA will end up into an infinite loop. Print Infinite loop! if so, or Successful! otherwise.
We only consider cases when d=2 for simplification. Note: s i g n ( x ) = { − 1 , x < 0 0 , x = 0 1 , x > 0 sign(x)=\begin{cases} -1,x<0\\[5ex] 0,x=0\\[5ex] 1,x>0 \end{cases} sign(x)=⎩⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎧−1,x<00,x=01,x>0 题意: 这题说得有模有样，其实就是让你判断是否存在一条直线将y=1与y=-1这两类点分隔开来，题解的正解答案是判断两类点的凸包是否相交 但是还有另外一种解法，因为数据较小可以这样做 附上大佬的题解https://www.cnblogs.com/widsom/p/11209955.html 思路:
#include<bits/stdc++.h> using namespace std; const int N=105; const double eps=1e-8; int x1[N],x2[N],y[N]; int main() { int T; scanf("%d",&T); while(T--) { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d%d",&x1[i],&x2[i],&y[i]); } double minn=-(1ll<<60),maxx=1ll<<60; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i==j||x2[i]==x2[j]) continue; if(y[i]==1&&y[j]==-1) { double t1=x2[j]-x2[i]; double t2=x1[i]-x1[j]; if(t1<0) minn=max(minn,t2/t1); else maxx=min(maxx,t2/t1); } } } if(fabs(maxx-minn)<=eps||maxx-minn>eps) { puts("Successful!"); continue; } minn=-(1ll<<60),maxx=1ll<<60; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i==j||x2[i]==x2[j]) continue; if(y[i]==1&&y[j]==-1) { double t1=x2[j]-x2[i]; double t2=-x1[i]+x1[j]; if(t1<0) minn=max(minn,t2/t1); else maxx=min(maxx,t2/t1); } } } if(fabs(maxx-minn)<=eps||maxx-minn>eps) { puts("Successful!"); } else puts("Infinite loop!"); } return 0; }