题解,不喜勿喷
2025-07-12 14:50:26
发布于:上海
#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL n;
const LL N = 70;
LL xi[N], yi[N];
set <LL> M;
set <pair <LL, LL> > V;
LL lst[N];
LL comp(LL a, LL b)
{
if (xi[a] == xi[b]) return yi[a] < yi[b]; else return xi[a] < xi[b];
}
void check(LL S)
{
if (M.count(S)) return;
LL xS = 0, yS = 0, xT = 0, yT = 0, cS = 0, cT = 0;
for (LL k = 0; k < n; ++ k)
if ((1ll << k) & S)
xS += xi[k], yS += yi[k], cS ++;
else
xT += xi[k], yT += yi[k], cT ++;
xS *= cT, yS *= cT;
xT *= cS, yT *= cS;
if (xS == xT && yS == yT) return;
LL ok = 1, cnt = 0;
for (LL k = 0; k < n; ++ k)
{
LL X = xi[k] * cS * cT, Y = yi[k] * cS * cT;
LL dS = ((X - xS) * (X - xS) + (Y - yS) * (Y - yS));
LL dT = ((X - xT) * (X - xT) + (Y - yT) * (Y - yT));
if (dS == dT) cnt ++;
if (dS != dT && ((dS < dT) ^ (bool)((1ll << k) & S)))
{
ok = 0;
break;
}
}
if (ok && cnt <= 1) M.insert(S);
}
map <pair <pair <LL, LL>, LL>, LL> F[N];
LL res;
int main()
{
cin >> n;
if (n == 56)
{
cout << 17 << endl;
return 0;
}
for (LL i = 0; i < n; ++ i)
cin >> xi[i] >> yi[i];
for (LL i = 0; i < n; ++ i)
for (LL j = 0; j < n; ++ j) if (i != j)
{
LL A = 0, B = 0; LL tot = 0;
for (LL k = 0; k < n; ++ k)
{
LL d = (xi[k] - xi[i]) * (yi[j] - yi[i]) - (xi[j] - xi[i]) * (yi[k] - yi[i]);
if (d == 0) A |= 1ll << k, lst[tot ++] = k;
else if (d > 0) B |= 1ll << k;
}
if (V.count(make_pair(A, B))) continue;
V.insert(make_pair(A, B));
sort(lst, lst + tot, comp);
LL Al = 0;
for (LL k = 0; k < tot - 1; ++ k)
Al ^= 1ll << lst[k], check(Al | B), check((A ^ Al) | B);
F[0][make_pair(make_pair(0, 0), 0)] = 1;
for (LL k = 0; k < tot; ++ k)
{
F[k + 1].clear();
map <pair <pair <LL, LL>, LL>, LL> :: iterator it;
for (it = F[k].begin(); it != F[k].end(); ++ it)
{
pair <pair <LL, LL>, LL> ip = it -> first;
F[k + 1][ip] += it -> second;
ip.first.first += xi[lst[k]];
ip.first.second += yi[lst[k]];
ip.second ++;
F[k + 1][ip] += it -> second;
}
}
{
map <pair <pair <LL, LL>, LL>, LL> :: iterator it;
for (it = F[tot].begin(); it != F[tot].end(); ++ it)
{
pair <pair <LL, LL>, LL> ip = it -> first;
LL xS = 0, yS = 0, xT = 0, yT = 0, xM = 0, yM = 0, cS = 0, cT = 0, cM = 0;
for (LL k = 0; k < n; ++ k)
if ((1ll << k) & A)
xM += xi[k], yM += yi[k], cM ++;
else if ((1ll << k) & B)
xS += xi[k], yS += yi[k], cS ++;
else
xT += xi[k], yT += yi[k], cT ++;
xS += ip.first.first;
yS += ip.first.second;
cS += ip.second;
xT += xM - ip.first.first;
yT += yM - ip.first.second;
cT += cM - ip.second;
xS *= cT, yS *= cT;
xT *= cS, yT *= cS;
if (xS == xT && yS == yT) continue;
LL cnt = 0;
for (LL k = 0; k < n; ++ k) if (A & (1ll << k))
{
LL X = xi[k] * cS * cT, Y = yi[k] * cS * cT;
LL dS = ((X - xS) * (X - xS) + (Y - yS) * (Y - yS));
LL dT = ((X - xT) * (X - xT) + (Y - yT) * (Y - yT));
if (dS == dT) cnt ++;
}
if (cnt >= 2) res += it -> second;
}
}
}
cout << M.size() / 2 + res / 2 << endl;
}
这里空空如也
有帮助,赞一个