Oblongs and Right Triangles 判断矩形 直角三角形

问题 B: Oblongs and Right Triangles

时间限制: 1 Sec  内存限制: 128 MB
提交: 31  解决: 4
[提交] [状态] [讨论版] [命题人:admin]

题目描述

There are N points on the plane; the i-th point is at (Xi, Yi). There may be multiple points at the same location. Four of the points will be coloured black and three other points will be coloured white. The remaining N − 7 points will be uncoloured.
An oblong is a rectangle that is not a square.
An right triangle is a triangle where one of the interior angles is exactly ninety degrees.
Determine the number of ways to colour the points such that the four black points are the vertices of an oblong and the three white points are the vertices of a right triangle. Note that both shapes should have positive area.

 

输入

Line 1 contains one integer N (7 ≤ N ≤ 24).
Line 2 contains N integers X1, . . . , XN ( − 229 ≤ Xi ≤ 229).
Line 3 contains N integers Y1, . . . , YN ( − 229 ≤ Yi ≤ 229).

 

输出

Print one line with one integer, the number of ways to choose an oblong and a right triangle.

 

样例输入

复制样例数据

8
-1 0 0 1 1 1 1 2
0 1 -1 0 -1 -1 -2 -1

样例输出

2

 

提示

The only way to form an oblong is with points 1,2,7,8. Of the remaining four points there are two ways to form a right triangle from them.

 

 

#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long ll;
const int maxn = 1e4 + 100;
const int inf = 0x3f3f3f3f;
typedef struct node {
    ll x, y;
} POINT;
POINT s[maxn];
struct noed {
    ll x1, x2, x3, x4;
    ll y1, y2, y3, y4;
    int p1, p2, p3, p4;
} p[maxn];
int vis[20];

ll dis(POINT a, POINT b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

bool mid(POINT a, POINT b, POINT c, POINT d) {
    if ((a.x + b.x == c.x + d.x) && (a.y + b.y == c.y + d.y)) return true;
    return false;
}

bool Rightangle(POINT a, POINT b, POINT c) {
    if ((b.x - a.x) * (b.x - c.x) + (b.y - a.y) * (b.y - c.y) == 0) return true;
    return false;
}

bool judge(POINT a, POINT b) {
    if (a.x == b.x && a.y == b.y) return true;
    return false;
}

bool checkoblong(POINT a, POINT b, POINT c, POINT d) {
    if (dis(a, b) > dis(a, c) && dis(a, b) > dis(a, d)) {
        if (dis(a, b) == dis(c, d) && mid(a, b, c, d) && dis(a, c) != dis(a, d))
            return true;
    }
    if (dis(a, c) > dis(a, b) && dis(a, c) > dis(a, d)) {
        if (dis(a, c) == dis(b, d) && mid(a, c, b, d) && dis(a, b) != dis(a, d))
            return true;
    }
    if (dis(a, d) > dis(a, c) && dis(a, d) > dis(a, b)) {
        if (dis(a, d) == dis(b, c) && mid(a, d, b, c) && dis(a, b) != dis(a, c))
            return true;
    }
    return false;
}

bool checktriangle(POINT a, POINT b, POINT c) {
    if (!judge(a,b) && !judge(a,c) && !judge(b,c)){
        if (Rightangle(a, b, c)) return true;
        if (Rightangle(a, c, b)) return true;
        if (Rightangle(b, a, c)) return true;
        return false;
    }
    return false;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &s[i].x);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &s[i].y);
    }
    int num = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (j == i) continue;
            for (int k = j + 1; k <= n; k++) {
                if (k == i || k == j) continue;
                for (int u = k + 1; u <= n; u++) {
                    if (u == i || u == j || u == k) continue;
                    if (checkoblong(s[i], s[j], s[k], s[u])) {
                        p[num].x1 = s[i].x, p[num].x2 = s[j].x, p[num].x3 = s[k].x, p[num].x4 = s[u].x;
                        p[num].y1 = s[i].y, p[num].y2 = s[j].y, p[num].y3 = s[k].y, p[num].y4 = s[u].y;
                        p[num].p1 = i, p[num].p2 = j, p[num].p3 = k, p[num++].p4 = u;
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int q = 0; q < num; q++) {
        vis[p[q].p1] = 1, vis[p[q].p2] = 1, vis[p[q].p3] = 1, vis[p[q].p4] = 1;
        for (int i = 1; i <= n; i++) {
            if (vis[i]) continue;
            for (int j = i + 1; j <= n; j++) {
                if (vis[j] || j == i) continue;
                for (int k = j + 1; k <= n; k++) {
                    if (vis[k] || j == i || j == k) continue;
                    if (checktriangle(s[i], s[j], s[k])) {
                        ans++;
                    }
                }
            }
        }
        vis[p[q].p1] = 0, vis[p[q].p2] = 0, vis[p[q].p3] = 0, vis[p[q].p4] = 0;
    }
    printf("%d\n", ans);
    return 0;
}