第六场问题 G: Greeting Card

题目描述

Quido plans to send a New Year greeting to his friend Hugo. He has recently acquired access to an advanced high-precision plotter and he is planning to print the greeting card on the plotter.
Here’s how the plotter operates. In step one, the plotter plots an intricate pattern of n dots on the paper. In step two, the picture in the greeting emerges when the plotter connects by a straight segment each pair of dots that are exactly 2 018 length units apart. 
The plotter uses a special holographic ink, which has a limited supply.Quido wants to know the number of all plotted segments in the picture to be sure that there is enough ink to complete the job.

输入

The first line of input contains a positive integer n specifying the number of plotted points. The following n lines each contain a pair of space-separated integer coordinates indicating one plotted point. Each coordinate is non-negative and less than 231. There are at most 105 points, all of them are distinct.
In this problem, all coordinates and distances are expressed in plotter length units, the length of the unit in the x-direction and in the y-direction is the same.

输出

The output contains a single integer equal to the number of pairs of points which are exactly 2018 length units apart.

样例输入

复制样例数据

4 20180000 20180000 20180000 20182018 20182018 20180000 20182018 20182018

样例输出

4

一开始思路是暴力，但是想想肯定会超时，这里方法比较像广搜中dir数组的用法，提前暴力计算一下如果两点距离为2018那么这两个点坐标之间的关系，不难得出这样的结论：如果两个点距离为2018 ，那么只能：①x距离差2018，y相等 ②x相等，y差2018 ③x差1680，y差1118 ④x差1118，y差1680。根据这四种情况，选取给的点，然后看看x和y相对位移这样一段距离后的点是否存在，如果存在说明选这两个点符合条件，计数加一。输出时应该除以二因为每条边实际上是计算了两次。
 

#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
const int maxn = 1e5+3;
typedef pair <ll,ll> pq;
map <pq,ll> m;
ll dir[12][2] = {2018,0,0,2018,-2018,0,0,-2018,1118,1680,-1118,1680,1118,-1680,-1118,-1680,1680,1118,1680,-1118,-1680,1118,-1680,-1118};
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,ans = 0;
    cin >> n;
    for(int i = 0;i < n; i++)
    {
        ll x,y;
        cin >> x >> y;
        ans += m[{x,y}];
        for(int i = 0;i < 12; i++)
            m[{x + dir[i][0],y + dir[i][1]}]++;
    }
    cout << ans << endl;
    return 0;
}