计算几何

目录

CSU 1007 矩形着色

CSU 1011: Counting Pixels

CSU 1159: 中南才女

CSU 1201: Triangle

CSU 1204 Rectangles

CSU 1403: 三角形面积

CSU 1407: 最短距离

CSU 1591: 三角形

CSU 1896: Symmetry(对称点集)

POJ 202 Squares

POJ 2002 Squares


CSU 1007 矩形着色

题目:


Description

Danni想为屏幕上的一个矩形着色,但是她想到了一个问题。当点击鼠标以后电脑是如何判断填充的区域呢?现在给你一个平面直角坐标系,其中有一个矩形和一个点,矩形的四条边均是平行于x轴或y轴的。请你判断这个点相对于矩形的位置,即在矩形内,在矩形上,还是在矩形外?
Input

第一行只有一个整数T,(T < 150),代表共有T种情况。

接下对于每种情况,均有两行数据:

第一行有两个整数Px Py,以空格分隔,代表点的坐标(Px,Py).

第二行有四个整数Ax Ay Bx By,以空格分隔,代表矩形左下角的坐标(Ax,Ay)和右上角的坐标(Bx,By).

所有的坐标均为区间[0,100]内的整数,且Ax<Bx,Ay<By

Output

对于每种情况仅输出一行:

1. 如果点在矩形外部,请输出”Outside”

2. 如果点正好在矩形的边上,请输出”On”

3. 如果点在矩形内部,请输出”Inside”

所有输出都不包含引号。

Sample Input

3
38 730 7 52 66
55 1
9 13 54 84
74 67
73 66 76 68
Sample Output

On
Outside
Inside

代码:

#include<iostream>
using namespace std;

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int px, py,ax, ay, bx, by;
		cin >> px >> py >> ax >> ay >> bx >> by;
		if (px<ax || px>bx || py<ay || py>by)cout << "Outside";
		else if (px == ax || px == bx || py == ay || py == by)cout << "On";
		else cout << "Inside";
		cout << endl;
	}
	return 0;
}

CSU 1011: Counting Pixels

题目:

Description
Did you know that if you draw a circle that fills the screen on your 1080p high definition display, almost a million pixels are lit? That's a lot of pixels! But do you know exactly how many pixels are lit? Let's find out!

Assume that our display is set on a Cartesian grid where every pixel is a perfect unit square. For example, one pixel occupies the area of a square with corners (0,0) and (1,1). A circle can be drawn by specifying its center in grid coordinates and its radius. On our display, a pixel is lit if any part of it is covered by the circle being drawn; pixels whose edge or corner are just touched by the circle, however, are not lit.

计算几何

Your job is to compute the exact number of pixels that are lit when a circle with a given position and radius is drawn.

Input
The input consists of several test cases, each on a separate line. Each test case consists of three integers, x,y, and r(1≤x,y,r≤1,000,000), specifying respectively the center (x,y) and radius of the circle drawn. Input is followed by a single line with x = y = r = 0, which should not be processed.

Output
For each test case, output on a single line the number of pixels that are lit when the specified circle is drawn. Assume that the entire circle will fit within the area of the display.

Sample Input
1 1 1
5 2 5
0 0 0
Sample Output
4
88

思路:

x和y是没用的,直接暴力求解加起来就行

代码:

#include<iostream>
#include<math.h>
using namespace std;
 
int main()
{
	long long r, ans;
	while (cin >> r >> r >> r)
	{
		if (r == 0)break;
		ans = 0;
		for (long long i = 0; i < r; i++)
			ans += int(sqrt(r*r - i * i) - 0.000000001) + 1;
		cout << ans * 4 << endl;
	}
	return 0;
}

CSU 1159: 中南才女

目:

Description

话说中南有位才女,叫做珊,学校里面很多同学都很喜欢她,想追她做女朋友。hkx也不例外。可是不知道为什么,向她表白的同学都一一落马,一向自卑的hkx一直也不敢表白,hkx得知珊有一天晚上8点钟以后的某段时间会去学校的某个地方弹吉他,可是hkx晚上9点以后才有时间去,虽然晚了一点,但也有机会,所以hkx就去了。

假设珊晚上到达的时刻是等可能的分布在8点到8+L点,hkx到达的时刻是等可能的分布在9点到9+L点。珊到达之后会在那里弹吉他t小时,之后就会离开。hkx到达之后如果没见到珊的话,他就会等上t小时,如果这t小时内珊还不出现,他就会离开。那么hkx能够见到珊的概率是多少呢?

Input
 多组数据,每组数据包括两个实数,L和t,一组数据占一行

1<=L<=10

0<=t<=10


Output
 输出hkx能够见到珊的概率,四舍五入到小数点后6位


Sample Input
2.0 0.0
2.0 3.0
Sample Output
0.000000
1.000000

这个题目其实好简单,就是在 1<y<1+L,0<x<L 这个正方形中,求满足 |y-x|<t 的部分所占的比例。

无非就是把直线y=x的下面和上面的部分分开求。

下面的部分是
sum = (l - 1)*(l - 1) / 2;
if (t < l - 1)sum -= (l - 1 - t)*(l - 1 - t) / 2;

上面的部分是

if (t < 1)sum += t*t / 2 + t*(l - 1);
else if(t<l+1)sum += l - 0.5 + l*l / 2 - (l - t + 1)*(l - t + 1) / 2;
else sum += l - 0.5 + l*l / 2;

完整代码:

#include<iostream>
#include<iomanip>
using namespace std;
 
int main()
{
	double  t, l, sum;
	while(cin >> l >> t)
	{
		sum = (l - 1)*(l - 1) / 2;
		if (t < l - 1)sum -= (l - 1 - t)*(l - 1 - t) / 2;
		if (t < 1)sum += t*t / 2 + t*(l - 1);
		else if(t<l+1)sum += l - 0.5 + l*l / 2 - (l - t + 1)*(l - t + 1) / 2;
		else sum += l - 0.5 + l*l / 2;
		cout << fixed << setprecision(6) << sum / l / l << endl;
	}
	return 0;
}

CSU 1201: Triangle

题目:

Description
已知三角形各边边长的取值范围,你能求出三角形最大的面积吗?

Input
输入数据的第一行包含一个整数T (1 <= T <= 200),表示接下来一共有T组测试数据。

每组数据占三行,每行均包含两个整数x, y (1 <= x <= y <= 1000),表示该边边长可以为[x, y]范围内的任意实数。

Output
用一行输出三角形的最大的面积,结果保留3位小数。如果三条边不能构成三角形,则用一行输出“No Triangle”(不包括引号)。

Sample Input
2
1 2
1 2
4 5
1 3
2 3
3 3
Sample Output
No Triangle
3.897

代码:
 

#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
 
struct node
{
	int x, y;
}nod[3];
 
double g(double a, double b, double c)
{
	double p = (a + b + c) / 2;
	return sqrt(p*(p - a)*(p - b)*(p - c));
}
 
double f(double a, int b, int x, int y)
{
	if (x >= a + b)	return -1;
	double s = sqrt(a*a + b*b);
	if (x > s)return g(a, b, x);
	if (y < s)return g(a, b, y);
	return a*b / 2;
}
 
int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d%d%d%d%d%d", &nod[0].x, &nod[0].y, &nod[1].x, &nod[1].y, &nod[2].x, &nod[2].y);
		int i1 = 0, i2 = 1, i3 = 2;
		if (nod[i1].y > nod[i2].y)i1 ^= i2 ^= i1 ^= i2;
		if (nod[i1].y > nod[i3].y)i1 ^= i3 ^= i1 ^= i3;
		if (nod[i2].y > nod[i3].y)i2 ^= i3 ^= i2 ^= i3;
		double r = f(nod[i1].y, nod[i2].y, nod[i3].x, nod[i3].y);
		if (r>-1)printf("%.3f\n", r);
		else printf("No Triangle\n");
	}
	return 0;
}

CSU 1204 Rectangles

题目:


Description

如果限定矩形的边长必须为整数,且周长为定值L,那么面积在[A, B]范围内不同的矩形一共有多少个呢?

在这个问题中,当且仅当两个矩形面积不同时,视作是两个不同的矩形。

Input

输入数据的第一行包含一个整数T (1 <= T <= 10000),表示接下来一共有T组测试数据。

对于每组测试数据,包含三个整数L (1 <= L <= 2,000,000,000)、A、B (1 <= A <= B <= 250,000,000,000,000,000),含义同上。

Output

对于每组测试数据,用一行输出一个整数,代表上述问题的答案。

Sample Input

3
11 1 6
12 5 10
12 8 10
Sample Output

0
3
2

这个题目,很明显是必须直接求出表达式,因为给的数太大了。

代码:
 

#include<iostream>
#include<math.h>
using namespace std;

int main()
{
	int T;
	cin >> T;
	long long a, b, l, max, min;
	while (T--)
	{
		cin >> l >> a >> b;
		if (l % 2)cout << 0 << endl;
		else
		{
			l = l / 2;
			max = l / 2;
			if (max*(l - max) > b)
			{
				max = (long long)(l*1.0 / 2 - sqrt(l*l*1.0 / 4 - b));
				if (max*(l - max) > b)max -= 1;
				else if ((max + 1)*(l - max - 1) <= b && max < l / 2)max += 1;
			}
			min = (l + 1) / 2;
			if (min*(l - min) == a)
			{
				cout << 1 << endl;
				continue;
			}
			if (min*(l - min) < a)
			{
				cout << 0 << endl;
				continue;
			}
			else
			{
				min = (long long)(l*1.0 / 2 - sqrt(l*l*1.0 / 4 - a)) + 1;
				if ((min - 1)*(l - min + 1) >= a)min -= 1;
				else if (min*(l - min)<a)min += 1;
			}
			if (max && min <= max)cout << max - min + 1 << endl;
			else cout << 0 << endl;
		}
	}
	return 0;
}

CSU 1403: 三角形面积

题目:

Description
给出三维空间上的三个点,计算以这三个点为顶点的三角形的面积。

Input
输入的第一行包含一个整数T (T > 0),表示一共有T组测试数据。
每组数据占三行,每行各描述了一个点的坐标。点的坐标会以x y z的形式给出,表示这个点的坐标为(x, y, z),其中x, y, z均为[-100, 100]范围内的浮点数。
Output
对于每组测试数据,输出三角形的面积(和标准答案的误差不超过10-6即可)。

Sample Input
2
0 1 0
1 0 0
0 0 0
0 0.0 1.00
1.0 0.00 0
0.00 1.0 0
Sample Output
0.50
0.8660254

代码:

 

#include<iostream>
#include<math.h>
#include<iomanip>
using namespace std;
 
int main()
{
	int t;
	double xa, ya, za, xb, yb, zb, xc, yc, zc;
	double l1, l2, l3, p;
	cin >> t;
	while (t--)
	{
		cin >> xa >> ya >> za >> xb >> yb >> zb >> xc >> yc >> zc;
		l1 = sqrt((xa - xb)*(xa - xb) + (ya - yb)*(ya - yb) + (za - zb)*(za - zb));
		l2 = sqrt((xa - xc)*(xa - xc) + (ya - yc)*(ya - yc) + (za - zc)*(za - zc));
		l3 = sqrt((xb - xc)*(xb - xc) + (yb - yc)*(yb - yc) + (zb - zc)*(zb - zc));
		p = (l1 + l2 + l3) / 2;
		cout << setprecision(16) << sqrt(p*(p - l1)*(p - l2)*(p - l3)) << endl;
	}
	return 0;
}

CSU 1407: 最短距离

题目:

Description
两个点 A ,  B 均在做匀速直线运动。给出 t  = 0时刻 A ,  B 的坐标,以及 A ,  B 的速度,计算 t  ≥  0时两个点的距离的最小值。
Input
输入的第一行包含一个整数 T  (1  ≤  T  ≤  200 ),表示一共有 T 组测试数据。
对于每组测试数据,第一行包含4个整数 x A ,  y A ,  v Ax ,  v Ay  (-10 3  ≤  x A ,  y A ,  v Ax ,  v Ay  ≤  10 3 ),表示 t  = 0时刻 A 的坐标为( x A ,  y A ), A 的速度在 x 轴方向上的分量为 v Ax ,在 y 轴上的分量为 v Ay 。第二行包含四个整数 x B ,  y B ,  v Bx ,  v By  (-10 3  ≤  x B ,  y B ,  v Bx ,  v By  ≤  10 3 ),以相同的方式给出了 B 的各项属性。
Output
对于每组测试数据,输出 t  ≥  0时两个点距离的最小值,保留8位小数。
Sample Input
6
0 0 0 0
0 1 0 1
0 0 -1 1
0 0 1 -1
0 1 1 0
2 0 0 1
0 1 1 0
2 0 1 0
0 0 -1 1
1 1 1 -1
997 997 -1000 -1000
-1000 -1000 1000 1000
Sample Output
1.00000000
0.00000000
0.70710678
2.23606798
1.41421356
0.00000000

代码:

#include<iostream>
#include<math.h>
#include<iomanip>
using namespace std;
 
int main()
{
	int t;
	double xa, ya, vxa, vya;
	double xb, yb, vxb, vyb;
	double a, b, c;//att+2bt+c
	cin >> t;
	while (t--)
	{
		cin >> xa >> ya >> vxa >> vya;
		cin >> xb >> yb >> vxb >> vyb;
		a = (vxa - vxb)*(vxa - vxb) + (vya - vyb)*(vya - vyb);
		b = (vxa - vxb)*(xa - xb) + (vya - vyb)*(ya - yb);
		c = (xa - xb)*(xa - xb) + (ya - yb)*(ya - yb);
		cout << setprecision(10) << sqrt((a*b >= 0) ? c : c - b * b / a) << endl;
	}
	return 0;
}

CSU 1591: 三角形

题目:

Description
star有n根火柴棒。由于他的火柴棒不是制式的,所以长度可能会不一样。现在star想选三根火柴棒搭一个三角形送给女朋友,并且希望三角形的面积尽量大。现在希望你编程告诉star可能搭成的最大三角形的面积是多少。

Input
第一行只有一个整数T(1<=T<=20),表示数据组数。
下面的T行每一行有一个整数n(3<=n<=100),表示火柴棒的数量,后面跟着n个整数Li(1<=Li<=100),表示n跟火柴棒的长度。

Output
对于每一组数据输出一个浮点数S,表示最大面积。
结果保留三位小数(四舍五入)。
如果无法搭成三角形,输出”no”。

Sample Input
3
3 3 4 5
4 3 4 5 5
3 1 1 2
Sample Output
6.000
9.165
no

代码:

#include<iostream>
#include<math.h>
#include<stdio.h>
using namespace std;
 
double f(int a, int b, int c)
{
	if (a + b <= c || a + c <= b || b + c <= a)return 0;
	double p = (a + b + c)*0.5;
	return sqrt(p*(p - a)*(p - b)*(p - c));
}
 
int main()
{
	int t, n, len[100];
	cin >> t;
	while (t--)
	{
		cin >> n;
		for (int i = 0; i < n; i++)cin >> len[i];
		double max = 0;
		for (int i = 0; i < n; i++)for (int j = i + 1; j < n; j++)for (int k = j + 1; k < n; k++)
			if (max < f(len[i], len[j], len[k]))max = f(len[i], len[j], len[k]);
		if (max)printf("%.3f\n", max);
		else cout << "no\n";
	}
	return 0;
}

CSU 1896: Symmetry(对称点集)

题目:


Description
We call a figure made of points is left-right symmetric as it is possible to fold the sheet of paper along a vertical line and to cut the figure into two identical halves.For example, if a figure exists five points, which respectively are (-2,5),(0,0),(2,3),(4,0),(6,5). Then we can find a vertical line x = 2 to satisfy this condition. But in another figure which are (0,0),(2,0),(2,2),(4,2), we can not find a vertical line to make this figure left-right symmetric.Write a program that determines whether a figure, drawn with dots, is left-right symmetric or not. The dots are all distinct.

Input
The input consists of T test cases. The number of test cases T is given in the first line of the input file. The first line of each test case contains an integer N, where N (1 <=N <= 1, 000) is the number of dots in a figure. Each of the following N lines contains the x-coordinate and y-coordinate of a dot. Both x-coordinates and y-coordinates are integers between −10, 000 and 10, 000, both inclusive.

Output
Print exactly one line for each test case. The line should contain 'YES' if the figure is left-right symmetric,and 'NO', otherwise.

Sample Input
3
5
-2 5
0 0
6 5
4 0
2 3
4
2 3
0 4
4 0
0 0
4
5 14
6 10
5 10
6 14
Sample Output
YES
NO
YES

这个题目是说,给一个整点集,判断是不是左右对称的。

要分2步进行,第一步找到唯一可能的对称轴的位置,第二步是判断点集是不是关于这条直线对称的。

第一步我是找最中间的若干个点,第二步我是把所有不在对称轴上面的点映射到一个整数,使得对称的点映射到一样的整数,不对称的点几乎不会映射到一样的整数,最后求出所有整数的异或,是0就对称,不是0就不对称。

我在比赛时提交的代码:
 

#include<iostream>
#include<algorithm>
using namespace std;
 
int kx1,kx2;
 
struct node
{
	int x,y;
};
 
bool cmp(node n1,node n2)
{
	return n1.x<n2.x;
}
 
int f(node nodd,int kx)
{
	if(nodd.x*2<kx)return (kx-nodd.x*2)%123*nodd.y;
	return (nodd.x*2-kx)%123*nodd.y;
}
 
int main()
{
	int T,N,ans1,ans2;
	node nod[1000];
	cin>>T;
	while(T--)
	{
		cin>>N;
		for(int i=0;i<N;i++)cin>>nod[i].x>>nod[i].y;
		sort(nod,nod+N,cmp);
		kx1=nod[N/2].x*2;
		kx2=nod[N/2].x+nod[(N-1)/2].x;
		ans1=ans2=0;
		for(int i=0;i<N;i++)
		{
			ans2=ans2^f(nod[i],kx2);
			if(nod[i].x==kx1)continue;
			ans1=ans1^f(nod[i],kx1);		
		}
		if(ans1==0||ans2==0)cout<<"YES\n";
		else cout<<"NO\n";
	}
	return 0;
}

实际上求对称轴还有更好的方法,不用最中间的点,用最左边和最右边的点。

第二步也不需要映射到整数,直接把点集存2份,一份从左往右排序,一份从右往左排序,然后一一比较是否对称即可。

新代码:

#include<iostream>
#include<algorithm>
using namespace std;
 
int T, N, kx;
struct node
{
	int x, y;
};
node nod1[1000], nod2[1000];
 
bool cmp1(node n1, node n2)
{
	if (n1.x == n2.x)return n1.y < n2.y;
	return n1.x<n2.x;
}
 
bool cmp2(node n1, node n2)
{
	if (n1.x == n2.x)return n1.y < n2.y;
	return n1.x>n2.x;
}
 
bool ok()
{
	for (int i = 0; i < N; i++)
	{
		if (nod1[i].y != nod2[i].y)return false;
		if (nod1[i].x + nod2[i].x != kx)return false;
	}
	return true;
}
 
int main()
{
	int left, right;
	cin >> T;
	while (T--)
	{
		cin >> N;
		left = 10000, right = -10000;
		for (int i = 0; i < N; i++)
		{
			cin >> nod1[i].x >> nod1[i].y;
			nod2[i].x = nod1[i].x, nod2[i].y = nod1[i].y;
			if (left>nod1[i].x)left = nod1[i].x;
			if (right < nod1[i].x)right = nod1[i].x;
		}
		kx = left + right;
		sort(nod1, nod1 + N, cmp1);
		sort(nod2, nod2 + N, cmp2);
		if (ok())cout << "YES\n";
		else cout << "NO\n";
	}
	return 0;
}

POJ 202 Squares

题目:


Description

A square is a 4-sided polygon whose sides have equal length and adjacent sides form 90-degree angles. It is also a polygon such that rotating about its centre by 90 degrees gives the same polygon. It is not the only polygon with the latter property, however, as a regular octagon also has this property. 

So we all know what a square looks like, but can we find all possible squares that can be formed from a set of stars in a night sky? To make the problem easier, we will assume that the night sky is a 2-dimensional plane, and each star is specified by its x and y coordinates. 
Input

The input consists of a number of test cases. Each test case starts with the integer n (1 <= n <= 1000) indicating the number of points to follow. Each of the next n lines specify the x and y coordinates (two integers) of each point. You may assume that the points are distinct and the magnitudes of the coordinates are less than 20000. The input is terminated when n = 0.
Output

For each test case, print on a line the number of squares one can form from the given stars.
Sample Input

4
1 0
0 1
1 1
0 0
9
0 0
1 0
2 0
0 2
1 2
2 2
0 1
1 1
2 1
4
-2 5
3 7
0 0
5 2
0
Sample Output

1
6
1

我感觉自己的做法挺好的啊啊,然而超时了

超时代码:

#include<iostream>
#include<algorithm>
#include<cmath>
#include<string.h>
using namespace std;
 
struct node
{
	long long sum, dx, dy;
};
 
long long point[1000];
long long h = 40001;
node nod[1000000];
 
bool cmp(node a, node b)
{
	return a.sum < b.sum;
}
 
long long getx(long long m)
{
	if (m >= 0)return m / h;
	else return (m + 1) / h - 1;
}
 
long long f(long long a, long long b)		//屏蔽掉对称性
{
	if (a > b)return a*h + b;
	return a + b*h;
}
 
int main()
{
	ios_base::sync_with_stdio(false);
	int n, x, y;
	while (cin >> n)
	{
		if (n == 0)break;
		for (int i = 0; i < n; i++)
		{
			cin >> x >> y;
			point[i] = x*h + y + h / 2;	//y + h / 2是0到4万, x*h + y + h / 2是大约-8亿到8亿
		}
		for (int i = 0; i < n*n; i++)
		{
			nod[i].sum = h *h * 2000000000;
			nod[i].dx = 0;
			nod[i].dy = 0;
		}
		for (int i = 0; i < n; i++)for (int j = i + 1; j < n; j++)
		{
			nod[i*n + j].dx = getx(point[i]) - getx(point[j]);
nod[i*n + j].dy = point[i] - getx(point[i])*h - (point[j] - getx(point[j])*h);
nod[i*n + j].sum = (point[i] + point[j])*h*h + f(abs(int(nod[i*n + j].dx)), abs(int(nod[i*n + j].dy)));//屏蔽掉正负
		}
		sort(nod, nod + n*n, cmp);
		int j, num = 0;
		for (int i = 1; i <= n*n; i++)
		{
			if (nod[i].sum == h *h * 2000000000)break;
			if (nod[i].sum == nod[i - 1].sum)	//满足这个的最多只有8种情况
			{
				j = i - 1;
				while (i <= n*n && nod[i].sum == nod[i - 1].sum)
				{
					for (int k = j; k < i; k++)
					{
			if (nod[k].dx == nod[i].dy && nod[k].dy == -nod[i].dx)num++;
			if (nod[k].dy == nod[i].dx && nod[k].dx == -nod[i].dy)num++;
					}
					i++;
				}
			}
		}
		cout << num << endl;
	}
	return 0;
}

POJ 2002 Squares

题目:


A square is a 4-sided polygon whose sides have equal length and adjacent sides form 90-degree angles. It is also a polygon such that rotating about its centre by 90 degrees gives the same polygon. It is not the only polygon with the latter property, however, as a regular octagon also has this property. 

So we all know what a square looks like, but can we find all possible squares that can be formed from a set of stars in a night sky? To make the problem easier, we will assume that the night sky is a 2-dimensional plane, and each star is specified by its x and y coordinates. 
Input
The input consists of a number of test cases. Each test case starts with the integer n (1 <= n <= 1000) indicating the number of points to follow. Each of the next n lines specify the x and y coordinates (two integers) of each point. You may assume that the points are distinct and the magnitudes of the coordinates are less than 20000. The input is terminated when n = 0.
Output
For each test case, print on a line the number of squares one can form from the given stars.
Sample Input
4
1 0
0 1
1 1
0 0
9
0 0
1 0
2 0
0 2
1 2
2 2
0 1
1 1
2 1
4
-2 5
3 7
0 0
5 2
0
Sample Output
1
6
1


题意:给出n个点,求出正方形数量

思路:枚举每2个点组成的线段,判断是不是正方形的对角线

代码:
 

#include<iostream>
#include<map>
using namespace std;
 
int N = 50000;
struct node
{
	int dx;
	int dy;
}nod[1005];
map<int,int>m;
 
int main()
{
	ios_base::sync_with_stdio(false);
	int n, x, y;
	while (cin >> n)
	{
		m.clear();
		if (n == 0)break;
		for (int i = 0; i < n; i++)
		{
			cin >> nod[i].dx >> nod[i].dy;
			m.insert(pair<int,int>(nod[i].dx*N+nod[i].dy,1));
		}
		int sum = 0;
		for (int i = 0; i < n; i++)for (int j = i+1; j < n; j++)
		{
			x = nod[i].dx + nod[j].dx + nod[i].dy - nod[j].dy;
			y = nod[i].dy + nod[j].dy + nod[j].dx - nod[i].dx;
			if (x % 2 || y % 2)continue;
			x /= 2, y /= 2;
			if (x > 20000 || x < -20000 || y>20000 || y < -20000)continue;
			if (m.find(x*N + y) == m.end())continue;
			x = nod[i].dx + nod[j].dx + nod[j].dy - nod[i].dy;
			y = nod[i].dy + nod[j].dy + nod[i].dx - nod[j].dx;
			if (x % 2 || y % 2)continue;
			x /= 2, y /= 2;
			if (x > 20000 || x < -20000 || y>20000 || y < -20000)continue;
			if (m.find(x*N + y) == m.end())continue;
			sum++;
		}
		cout << sum/2 << endl;
	}
	return 0;
}

 

上一篇:Docem工具


下一篇:PyTorch写代码的一些技巧和常用操作(持续更新)