gym101573I Favorite Points
纪念一下。
#include<bits/stdc++.h>
#define LL long long
#define PLL pair<LL, LL>
#define MP make_pair
#define EB emplace_back
#define all(x) x.begin(), x.end()
using namespace std;
template<typename T> void chkmn(T &a, const T &b) { (a > b) && (a = b); }
template<typename T> void chkmx(T &a, const T &b) { (a < b) && (a = b); }
const int N = 1005;
LL sqr(LL x) { return x * x; }
struct Hood // Point
{
LL x, y;
Hood(LL x = 0, LL y = 0) : x(x), y(y) {}
friend Hood operator + (const Hood &A, const Hood &B) { return Hood(A.x + B.x, A.y + B.y); }
friend Hood operator - (const Hood &A, const Hood &B) { return Hood(A.x - B.x, A.y - B.y); }
friend Hood operator * (const Hood &A, const LL &dango) { return Hood(A.x * dango, A.y * dango); }
friend Hood operator / (const Hood &A, const LL &dango) { return Hood(A.x / dango, A.y / dango); }
Hood &operator += (const Hood &u) { x += u.x, y += u.y; return *this; }
Hood &operator -= (const Hood &u) { x -= u.x, y -= u.y; return *this; }
Hood &operator *= (const LL dango) { x *= dango, y *= dango; return *this; }
Hood &operator /= (const LL dango) { x /= dango, y /= dango; return *this; }
friend Hood operator * (LL dango, Hood u) { return Hood(u.x * dango, u.y * dango); }
LL sqrlen() { return sqr(x) + sqr(y); }
void read() { cin >> x >> y; }
}p[N];
Hood a[N * N]; // line
LL gcd(LL a, LL b)
{
if(!b) return a;
return gcd(b, a % b);
}
int n, m;
LL ans1, ans2, ans3, ans4, rec;
void dealsign(LL &x, LL &y)
{
if(x < 0) x = -x, y = -y;
else if(x == 0 && y < 0) y = -y;
}
// vector
map<PLL, LL> mp1; // Parallelograms inc
// k, b, length
map<pair<pair<PLL, PLL>, LL>, LL> mp2; // Parallelograms dec
// x, length
map<PLL, LL> mp3; // Parallelograms dec (vertical)
void Parallelograms()
{
for(int i = 1; i <= n; ++i)
for(int j = i + 1; j <= n; ++j)
{
a[++m] = p[i] - p[j];
dealsign(a[m].x, a[m].y);
mp1[MP(a[m].x, a[m].y)]++;
LL len = a[m].sqrlen();
if(p[i].x == p[j].x) mp3[MP(p[i].x, len)]++;
else
{
LL w1, w2, w3, w4, d;
w1 = p[j].y - p[i].y;
w2 = p[j].x - p[i].x;
d = gcd(w1, w2);
w1 /= d, w2 /= d;
dealsign(w1, w2);
w3 = p[j].x * p[i].y - p[i].x * p[j].y;
w4 = p[j].x - p[i].x;
d = gcd(w3, w4);
w3 /= d, w4 /= d;
dealsign(w3, w4);
mp2[MP(MP(MP(w1, w2), MP(w3, w4)), len)]++;
}
}
for(map<PLL, LL>::iterator it = mp1.begin(); it != mp1.end(); ++it)
{ LL w = it->second; ans1 += w * (w - 1) / 2; }
for(map<pair<pair<PLL, PLL>, LL>, LL>::iterator it = mp2.begin(); it != mp2.end(); ++it)
{ LL w = it->second; ans1 -= w * (w - 1) / 2; }
for(map<PLL, LL>::iterator it = mp3.begin(); it != mp3.end(); ++it)
{ LL w = it->second; ans1 -= w * (w - 1) / 2; }
ans1 /= 2;
mp1.clear();
mp2.clear();
mp3.clear();
}
//vector
map<PLL, LL> mp4; // Trapezoids inc
// k, b
map<pair<PLL, PLL>, LL> mp5; // Trapezoids dec
// x
map<LL, LL> mp6; // Trapezoids dec (vertical)
void Trapezoids()
{
LL res = 0;
for(int i = 1; i <= m; ++i)
{
LL w1 = a[i].y, w2 = a[i].x;
LL d = gcd(w1, w2);
w1 /= d, w2 /= d;
dealsign(w1, w2);
mp4[MP(w1, w2)]++;
}
for(int i = 1; i <= n; ++i)
for(int j = i + 1; j <= n; ++j)
{
if(p[i].x == p[j].x) mp6[p[i].x]++;
else
{
LL w1, w2, w3, w4, d;
w1 = p[j].y - p[i].y;
w2 = p[j].x - p[i].x;
d = gcd(w1, w2);
w1 /= d, w2 /= d;
dealsign(w1, w2);
w3 = p[j].x * p[i].y - p[i].x * p[j].y;
w4 = p[j].x - p[i].x;
d = gcd(w3, w4);
w3 /= d, w4 /= d;
dealsign(w3, w4);
mp5[MP(MP(w1, w2), MP(w3, w4))]++;
}
}
for(map<PLL, LL>::iterator it = mp4.begin(); it != mp4.end(); ++it)
{ LL w = it->second; res += w * (w - 1) / 2; }
for(map<pair<PLL, PLL>, LL>::iterator it = mp5.begin(); it != mp5.end(); ++it)
{ LL w = it->second; res -= w * (w - 1) / 2; }
for(map<LL, LL>::iterator it = mp6.begin(); it != mp6.end(); ++it)
{ LL w = it->second; res -= w * (w - 1) / 2; }
// printf("res : %lld\n", res);
ans4 = res - 2 * ans1;
mp4.clear();
mp5.clear();
mp6.clear();
}
// count by fiagonals
// k, mid(*2)
map<pair<PLL, PLL>, LL> mp7; // Rhombuses inc
// mid(*2)
map<PLL, LL> mp8; // Rhombuses inc(vertical)
void Rhombuses()
{
for(int i = 1; i <= n; ++i)
for(int j = i + 1; j <= n; ++j)
{
LL midx = p[i].x + p[j].x;
LL midy = p[i].y + p[j].y;
if(p[i].x == p[j].x) mp8[MP(midx, midy)]++;
else
{
LL w1 = p[j].y - p[i].y;
LL w2 = p[j].x - p[i].x;
LL d = gcd(w1, w2);
w1 /= d, w2 /= d;
dealsign(w1, w2);
mp7[MP(MP(w1, w2), MP(midx, midy))]++;
}
}
for(int i = 1; i <= n; ++i)
for(int j = i + 1; j <= n; ++j)
{
LL midx = p[i].x + p[j].x;
LL midy = p[i].y + p[j].y;
if(p[i].y == p[j].y)
ans2 += mp8[MP(midx, midy)];
else
{
PLL k = MP(p[i].x - p[j].x, p[j].y - p[i].y);
LL d = gcd(k.first, k.second);
k.first /= d, k.second /= d;
dealsign(k.first, k.second);
ans2 += mp7[MP(k, MP(midx, midy))];
}
}
ans2 /= 2;
mp7.clear();
mp8.clear();
}
// count by diagonals
// k, mid(*2), length
map<pair<pair<PLL, PLL>, LL>, LL> mp9; // Squares inc
// mid(*2), length
map<pair<PLL, LL>, LL> mp0; // Squares inc(vertical)
void Squares()
{
for(int i = 1; i <= n; ++i)
for(int j = i + 1; j <= n; ++j)
{
LL midx = p[i].x + p[j].x;
LL midy = p[i].y + p[j].y;
LL len = sqr(p[i].x - p[j].x) + sqr(p[i].y - p[j].y);
if(p[i].x == p[j].x) mp0[MP(MP(midx, midy), len)]++;
else
{
LL w1 = p[j].y - p[i].y;
LL w2 = p[j].x - p[i].x;
LL d = gcd(w1, w2);
w1 /= d, w2 /= d;
dealsign(w1, w2);
mp9[MP(MP(MP(w1, w2), MP(midx, midy)), len)]++;
}
}
for(int i = 1; i <= n; ++i)
for(int j = i + 1; j <= n; ++j)
{
LL midx = p[i].x + p[j].x;
LL midy = p[i].y + p[j].y;
LL len = sqr(p[i].x - p[j].x) + sqr(p[i].y - p[j].y);
if(p[i].y == p[j].y)
ans3 += mp0[MP(MP(midx, midy), len)];
else
{
PLL k = MP(p[i].x - p[j].x, p[j].y - p[i].y);
LL d = gcd(k.first, k.second);
k.first /= d, k.second /= d;
dealsign(k.first, k.second);
ans3 += mp9[MP(MP(k, MP(midx, midy)), len)];
}
}
ans3 /= 2;
mp9.clear();
mp0.clear();
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
p[i].read();
Parallelograms();
Rhombuses();
Squares();
Trapezoids();
printf("Parallelograms: %lld\n", ans1);
printf("Rhombuses: %lld\n", ans2);
printf("Squares: %lld\n", ans3);
printf("Trapezoids: %lld\n", ans4);
return 0;
}
//8
//0 0
//0 1
//0 2
//1 0
//1 1
//1 2
//2 0
//2 1
// 9
// 0 0
// 0 1
// 0 2
// 1 0
// 1 1
// 1 2
// 2 0
// 2 1
// 2 2
//5
//0 0
//0 2
//2 0
//2 2
//1 1
//4
//2 1
//1 -2
//-2 -1
//-1 2