[学习笔记]2018/2/27

oi
  1. 1. [学习笔记]2018/2/27
    1. 1.1. poj2002
      1. 1.1.1. Squares
      2. 1.1.2. Sample Input
      3. 1.1.3. Sample Output
      4. 1.1.4. Source
      5. 1.1.5. 题解

[学习笔记]2018/2/27


今天主要在搞模板,就没有怎么做题
a了一个水题..但做的并不是很轻松

poj2002

Squares

Time Limit: 3500MS Memory Limit: 65536K
Total Submissions: 20965 Accepted: 8063
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

Source

Rocky Mountain 2004

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <deque>

using namespace std;

namespace solve
{

inline int read()
{
char c = getchar();
int ret = 0, f = 1;

for (; !isdigit(c);
f = c == '-' ? -1 : 1, c = getchar());

for (; isdigit(c);
ret = ret * 10 + c - '0', c = getchar());

return ret * f;
}

const int maxn = 1005;
const int mod = 105;
int n;
int a, b;
vector<pair<int, int> > lst[mod];
vector<pair<int, int> > all;

inline int hash(pair<int, int> p)
{
int x = (long long)(p.first * p.second) % mod;
int s = (p.first + p.second) % mod;
return abs(x + s) % mod;
}

inline void insert(pair<int, int> p)
{
lst[hash(p)].push_back(p);
}

inline bool exist(pair<int, int> p)
{
int hashrs = hash(p);

for (int i = 0; i < lst[hashrs].size(); ++i)
if (lst[hashrs][i] == p) return true;

return false;
}

inline void solve()
{
for (;;)
{
n = read();

if (n == 0) break;

int cnt = 0;

for (int i = 0; i < n; ++i)
{
a = read(), b = read();
all.push_back(make_pair(a, b));
insert(make_pair(a, b));
}

for (register int i = 0; i < all.size(); ++i)
{
for (register int j = i + 1; j < all.size(); ++j)
{
bool ext = false;
pair<int, int>& p1 = all[i];
pair<int, int>& p2 = all[j];
int suby = p2.second - p1.second;
int subx = p2.first - p1.first;
int tempx = p1.first + suby;
int tempy = p1.second - subx;
int tempx1 = p2.first + suby;
int tempy1 = p2.second - subx;
if(exist(make_pair(tempx, tempy)) && exist(make_pair(tempx1, tempy1))) ++cnt;
tempx = p1.first - suby;
tempy = p1.second + subx;
tempx1 = p2.first - suby;
tempy1 = p2.second + subx;
if(exist(make_pair(tempx, tempy)) && exist(make_pair(tempx1, tempy1))) ++cnt;
}
}
cout << cnt / 4 << endl;
for (int i = 0; i < mod; ++i) lst[i].resize(0);
all.resize(0);
}
}
}
int main()
{
solve::solve();
return 0;
}