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