首页 > 其他分享 >gym101573I Favorite Points

gym101573I Favorite Points

时间：2023-07-06 14:57:10浏览次数：34  
标签：map const gym101573I LL Favorite Points dango return Hood

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

标签：map,const,gym101573I,LL,Favorite,Points,dango,return,Hood
From： https://www.cnblogs.com/Schucking-Sattin/p/17532114.html

相关文章

  • 1595. Minimum Cost to Connect Two Groups of Points] (Hard)
    Description1595.MinimumCosttoConnectTwoGroupsofPoints(Hard)Youaregiventwogroupsofpointswherethefirstgrouphassize1points,thesecondgrouphassize2points,andsize1>=size2.Thecostoftheconnectionbetweenanytwopointsar......
  • CF19D. Points
    感觉不难啊，为什么是*2800捏。先离散化。对每个横坐标开一个set存点，插入删除就能做了。查询的时候线段树二分就行了。更具体地，我们维护区间内纵坐标的最大值，在二分的时候能左就左，不能左就右。注意这里的右上角是严格大于。点击查看代码#include<bits/stdc++.h>#definei......
  • 如何查看在当前的ingress-controller中，有哪些backend?每个backend的endpoints是什么？
    通过kubectlingress-nginx命令，可以查看在ingresscontroller中，有哪些backends，每个backends的后端的endpoints信息和对应其他的参数设置 比如： kubectlingress-nginxbackends-ningress-nginx  [root@nccztsjb-node-23data]#kubectlingress-nginxbackends-n......
  • Visible Lattice Points 题解
    VisibleLatticePoints题目大意给定一个\(N×N×N\)的由若干点组成的立方体，点的坐标从\((0,0,0)\)到\((N,N,N)\)，求从点\((0,0,0)\)处可以看见多少个点。思路分析我们将立方体上的点分成三类：在\(xy,yz,xz\)平面上的点。在\(x,y,z\)轴上的点。即不在平面，也不在......
  • Sep 2022-Prioritized Training on Points that are Learnable, Worth Learning, and
    摘要：对网络规模的数据进行训练可能需要数月时间。但大多数计算和时间都浪费在已经学习或无法学习的冗余和噪声点上。为加速训练，本文提出了ReducibleHoldoutLossSelection(RHOLOSS)，一种简单但有原则的技术，近似地选择那些最能减少模型泛化损失的点进行训练。因此，rho损失缓解了现......
  • 牛客 55994 2023牛客五一集训派对day3 D Points Construction Problem
    D-PointsConstructionProblem_2023牛客五一集训派对day3(nowcoder.com)将图上恰好\(n\)个点染成黑色，使得图上相邻的黑白点对数量恰好为\(m\)考虑\(n\)个黑点如果不相邻，则两个点的贡献互不影响考虑相邻的情况，我们把相邻的点连边，则贡献为每一个连通块的贡献的和，我们用......
  • image as set of points
    ImageAsSetOfPointsAbstract提取图像特征的几种方法:ConvNets:将图像视为矩形中有组织的像素，并通过局部区域的卷积运算提取特征；VisionTransformers(ViTs):将图像视为一系列补丁，并通过全局范围内的注意力机制提取特征。ContextClusters(CoCs):上下文聚类将图像视为一组......
  • hdu 5442 长春区域赛网络赛 1006 Favorite Donut(后缀数组)
    题目链接：hdu5442题目大意：给出一个环，每颗珠子有一个甜度，选择第一个珠子和吃的方向，问得到的吃珠子的字符串的字典序最大的，如果有多个，选取位置最靠前的，如果还是多个，选择顺时针吃的。题目分析：-首先构造一个字符串，首先正着按环吃，那么就是字符串正着写两遍，连接在一起;中间用没有出现过的......
  • UVA How Many Points of Intersection?
      HowManyPointsofIntersection? a dotsonthetoprowand b dotsonthebottomrow.Wedrawlinesegmentsconnectingeverydotonthetoprowwitheverydotonthebottomrow.Thedotsarearrangedinsuchawaythatthenumberofinternalintersectio......
  • poj 3090 Visible Lattice Points
     #include<iostream>#include<algorithm>usingnamespacestd;constintM=1e6;intvis[M+4],P[M+4],cnt;intfi[M+4];voidshai(inttop){ cnt=0; fi[1]=1; for(inti=2;i<=top;i++){ if(vis[i]==0){ P[++cnt]=i; fi[i]=i-1;......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99