\({\rm fish}\)
20分：
六个for，点积判锐角钝角。
#include #include #include #include #include #include #include #define LL long long#define uint unsigned int#define debug(...) fprintf(stderr, __VA_ARGS__)#define GO debug("GO\n")#define rep(i, a, b) for (register uint (i) = (a); (i) <= (b); ++ (i))#define dep(i, a, b) for (register uint (i) = (a); (i) >= (b); -- (i))namespace io { const char endl = '\n'; template inline void chkmin(T &a, T b) { a > b ? a = b : 0; } template inline void chkmax(T &a, T b) { a < b ? a = b : 0; } struct Stream { template Stream operator>> (T &x) { register int f = 1; register char c; while (!isdigit(c = getchar())) if (c == '-') f = -1; while (x = (x << 1) + (x << 3) + (c ^ 48), isdigit(c = getchar())); return x *= f, *this; } Stream operator>> (char *str) { return scanf("%s", str), *this; } template Stream operator<< (T x) { static char out[35]; static uint top = 0; if (x < 0) x = -x, out[++top] = '-'; while (out[++top] = x % 10 ^ 48, x /= 10, x); while (putchar(out[top--]), top); return *this; } Stream operator<< (char *str) { return printf("%s", str), *this; } Stream operator<< (char ch) { return putchar(ch), *this; } } cin, cout;}const int N = 20;struct Vector { int x, y; Vector() {} Vector(int _x, int _y) { x = _x, y = _y; } Vector operator-(Vector B) { return Vector(x - B.x, y - B.y); } Vector operator+(Vector B) { return Vector(x + B.x, y - B.y); } int operator*(Vector B) { return x * B.x + y * B.y; } int len2() { return x * x + y * y; }} P[N];int main() {#ifndef ONLINE_JUDGE freopen("xhc.in", "r", stdin); freopen("xhc.out", "w", stdout);#endif register int n, ans = 0; std::cin >> n; rep(i, 1, n) std::cin >> P[i].x >> P[i].y; rep(A, 1, n) rep(B, 1, n) rep(C, 1, n) rep(D, 1, n) rep(E, 1, n) rep(F, 1, n) { if (A == B || A == C || A == D || A == E || A == F) continue; if (B == C || B == D || B == E || D == F) continue; if (C == D || C == E || C == F) continue; if (D == E || D == F) continue; if (E == F) continue; if ((P[B] - P[A]) * (P[D] - P[A]) > 0 and (P[D] - P[A]) * (P[C] - P[A]) > 0 and (P[B] - P[D]) * (P[A] - P[D]) > 0 and (P[C] - P[D]) * (P[A] - P[D]) > 0 and (P[A] - P[D]) * (P[E] - P[D]) < 0 and (P[A] - P[D]) * (P[F] - P[D]) < 0 and (P[A] - P[B]).len2() == (P[A] - P[C]).len2() and (P[B] - P[D]).len2 ()== (P[D] - P[C]).len2() and (P[E] - P[D]).len2() == (P[D] - P[F]).len2()) { ans ++; } } io::cout << ans << io::endl; return 0;}
40分：
对着题面中的图讲，
第一部分：
枚举 (A, D) 然后再枚举 P (形如E,F的点)将所有 PD 满足 角ADP 为钝角的 PD 的长扔进一个 vector，
然后 sort，用 f[A][D] 表示 AD 为脊柱，的尾巴数量，由于 sort 了，很好计算出来。
再用 map 实现一个 AD斜率->vector 的映射，vector存斜率为这个的(A, D)。
第二部分：
枚举 (B, C) ，求出 AD斜率 (垂直) ，到 对应的斜率的vector (map映射)中寻找符合题意的 (A, D) ，然后 Ans 加上 f[A][D].
根据题意，最后 Ans *= 4.
#include #include
100分
40分复杂度的瓶颈在于计算以AD为脊柱的尾巴的个数，由于我们发现合法的尾巴只可能在垂直AD的直线的右侧，所以考虑先枚举D，按极角排序，再枚举A，让A围着D逆时针转，同时维护合法平面内的尾巴数量，维护的方式与莫队的方法类似。
然后同样枚举AD，为了为了快速求出合法的BC的数量，需要事先处理出任意两点中垂线的解析式，那么鱼的脊柱肯定在BC的中垂线上，所以枚举AD时，通过对AD这条直线所包含的点二分查找就可以知道有多少对BC，再乘以尾巴的数量即可，这里的实现比较复杂，用map映射直线所代表的vector，vector存BC的中点，具体难以描述, 细节就是特判没有斜率的情况。
#include #include