题目链接：
UVALive 6693 - Flow Game
题意：
给一个 n?n 的方格和方格边界上的四个点，分别标号是1，1，2，2代表两条折线段的起点和终点，问将折线段连接且不相交的最短距离是多少?相交时输出 ?1 。
分析：
主要是点在同一条边时的特判比较麻烦。
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;int t, n, ans;struct NODE {int x, y;NODE () {}NODE (int _x, int _y) : x(_x), y(_y) {}NODE operator - (const NODE& a) const {return NODE(x - a.x, y - a.y);}int cross(const NODE& rhs) const {return x * rhs.y - y * rhs.x;}int dot(const NODE& rhs) const{return x * rhs.x + y * rhs.y;}
}node[10];struct Line {NODE s, e;Line() {}Line(NODE _s, NODE _e) : s(_s), e(_e) {}int relation(const NODE& rhs) const {int res = (rhs - s).cross(e - s);if(res == 0) return 0;else if(res > 0) return 1;else return -1;}bool point_on_seg(const NODE& rhs) const { //点在线段上的判断return (rhs - s).cross(e - s) == 0 && (rhs - s).dot(rhs - e) <= 0;}
};void print(int add)
{int ans = 0;ans = abs(node[1].x - node[0].x) + abs(node[1].y - node[0].y);ans += abs(node[3].x - node[2].x) + abs(node[3].y - node[2].y) + 2;if(add != -1) cout << ans + add << endl;else cout << -1 << endl;
}int main()
{cin >> t;while(t--){cin >> n;set<int> sx, sy;int cnt1 = 0, cnt2 = 2;for(int i = 1; i <= n; ++i){char tmp[12];scanf("%s", tmp + 1);for(int j = 1; j <= n; ++j){if(tmp[j] == '1'){node[cnt1].x = i;node[cnt1++].y = j;sx.insert(i), sy.insert(j);}else if(tmp[j] == '2'){node[cnt2].x = i;node[cnt2++].y = j;sx.insert(i), sy.insert(j);}}} int ok = 0, flag1 = 0, flag2 = 0, flag3 = 0, flag4 = 0;Line line1 = Line(node[0], node[1]), line2 = Line(node[2], node[3]);if(line1.point_on_seg(node[2])) flag1 = 1;if(line1.point_on_seg(node[3])) flag2 = 1;if(line2.point_on_seg(node[0])) flag3 = 1;if(line2.point_on_seg(node[1])) flag4 = 1;if(flag1 && flag2) {print(2);continue;}if(flag1 && !flag2) {cout << -1 << endl;continue;}if(!flag1 && flag2) {cout << -1 << endl;continue;}if(flag3 && flag4) {print(2);continue;}if(flag3 && !flag4) {cout << -1 << endl;continue;}if(!flag3 && flag4) {cout << -1 << endl;continue;}int t1 = line1.relation(node[2]), t2 = line1.relation(node[3]);if(t1 != t2 && t1 && t2) cout << -1 << endl;else print(0);}return 0;
}