前置知识

(1) 求两条线段的交点

方法1, 运用高中的解析几何知识求.
方法2, 运用向量点积求.
考虑向量叉乘。若 \(\vec a\times\vec b>0\), 那么 \(\vec b\)在 \(\vec a\) 的逆时针方向；若叉积小于 \(0\)，那么 \(\vec b\)在 \(\vec a\) 的顺时针方向。于是，判断点 C 和 D 是否在直线 AB 的两侧，就是判断 \(\overrightarrow{AB}\times\overrightarrow{AC}\)和 \(\overrightarrow{AB}\times\overrightarrow{AD}\)是否同号。如果同号，那么在同侧；如果异号，那么在两侧。题目保证了任意三点不共线，所以叉积为 0 的情况不可能出现。(copy from be60_)

(2) DFS

由于本题数据范围太小了, 可以用无脑STL的next_permutation搞. 不难做.

Code

#include <bits/stdc++.h>
using namespace std;
#define F(i, a, b) for(int i=a; i<=b;i++)
#define Fd(i, a, b) for(int i=a;i>=b;i--)
#define D double
#define MAXN 10
#define printf blank
#define eps (1e-9)
#define pb push_back
#define ppp pair<Point, Point> 
void blank(...){}
struct Point{
	int x, y; 
	Point(double x=0, double y=0): x(x), y(y){}
};
vector<Point> v;

Point operator-(Point a,Point b){return Point(a.x-b.x,a.y-b.y);}
D cross(Point a, Point b){
	return ((D)(a.x*b.y-a.y*b.x));
}
int dcmp(D x){return fabs(x)<eps?0:(x<0?-1:1);}
bool interc(Point a1, Point a2, Point b1, Point b2){
	double c1=cross(a2-a1,b1-a1);
	double c2=cross(a2-a1,b2-a1);
	double c3=cross(b2-b1,a1-b1);
	double c4=cross(b2-b1,a2-b1);
    return dcmp(c1)*dcmp(c2)<0&&dcmp(c3)*dcmp(c4)<0;
}
int s[10]={0,1,2,3,4,5,6,7,8,9};
int cnt=1, num=0;
bool chk(){
	vector<pair<Point, Point> > now;
	now.clear();
	F(i, 1, cnt-1){
		ppp nxt = make_pair(v[s[i]], v[s[i-1]]);
		for(ppp i : now){
			if(interc(i.first, i.second, nxt.first, nxt.second)){
				return 0;
			}
		}
		now.pb(nxt);
	}
	ppp nxt = make_pair(v[0], v[s[cnt-1]]);
	for(ppp i : now){
			if(interc(i.first, i.second, nxt.first, nxt.second)){
				return 0;
			}
	}
	return 1;
}

int main(){
	int m, n; 
	cin>>m>>n;
	v.pb(Point(0,0));
	while(m != 0 || n != 0){
		cnt++;
		Point p(m, n);
		v.pb(p);
		cin>>m>>n;
		
	}
	
	#define UPDATE if(chk()) {num++; printf("SUCCESS\n");}else{printf("FAIL\n");}
	UPDATE
	while(next_permutation(s+1, s+cnt)){
		UPDATE
	}
	
	cout<<num/2<<endl;
	
	
}

错在哪

第一次没有考虑全面, 最后一条线也要完全做, 因此没有考虑最后一条线和第一条线的关系.