95 lines
2.7 KiB
C++
95 lines
2.7 KiB
C++
#include <bits/stdc++.h>
|
||
const int N = 110;
|
||
char a[N][N];
|
||
|
||
using namespace std;
|
||
const double eps = 1e-8;
|
||
int n;
|
||
struct Node {
|
||
int x, y;
|
||
char c;
|
||
};
|
||
vector<Node> q;
|
||
|
||
/*
|
||
4
|
||
abccddadca
|
||
|
||
2
|
||
aaa
|
||
*/
|
||
/*
|
||
把半径当做 1 ，建立坐标系，然后枚举就行了，需要注意的是，在判断三条边的长度是否相等时用 double 牵扯到精度问题，
|
||
解决方法是:比较长度的平方，长度的平方肯定是整数，还有就是层层之间纵坐标相差是sqrt(3) 的倍数，
|
||
为了不牵扯到小数，把纵坐标的 sqrt(3) 当做1 ，求边长时乘三即可。
|
||
|
||
|
||
共n=4行
|
||
第一行第一个3,3*sqrt(3)
|
||
第二行第一个:2,2*sqrt(3) 第二行第二个: 2+2,2*sqrt(3)
|
||
第三行第一个:1,1*sqrt(3) 第三行第二个: 1+2,1*sqrt(3) 第三行第三个:1+2+2,1*sqrt(3)
|
||
第四行第一个:0,0 第四行第二个:0+2,0 第四行第三个:0+2+2,0 第四行第四个:0+2+2+2,0
|
||
|
||
规律
|
||
第i行，第j个
|
||
i从1开始，到n=4结束
|
||
j从1开始，到i结束
|
||
找出递推关系式：
|
||
x=n-i + (j-1)*2
|
||
y=(n-i)*sqrt(3)
|
||
*/
|
||
|
||
bool check(Node a, Node b, Node c) {
|
||
// x= n - i + (j - 1) * 2
|
||
// y= (n - i) * sqrt(3)
|
||
if (a.c != b.c || a.c != c.c || b.c != c.c) return false;
|
||
|
||
double ax = (n - a.x + (a.y - 1) * 2);
|
||
double bx = (n - b.x + (b.y - 1) * 2);
|
||
double cx = (n - c.x + (c.y - 1) * 2);
|
||
|
||
double ay = (n - a.x) * sqrt(3);
|
||
double by = (n - b.x) * sqrt(3);
|
||
double cy = (n - c.x) * sqrt(3);
|
||
|
||
double c1 = (ax - bx) * (ax - bx) + (ay - by) * (ay - by);
|
||
double c2 = (ax - cx) * (ax - cx) + (ay - cy) * (ay - cy);
|
||
double c3 = (bx - cx) * (bx - cx) + (by - cy) * (by - cy);
|
||
if (abs(c1 - c2) < eps && abs(c1 - c3) < eps && abs(c2 - c3) < eps) return true;
|
||
return false;
|
||
}
|
||
|
||
int main() {
|
||
#ifndef ONLINE_JUDGE
|
||
freopen("51nod_1909_2_in.txt", "r", stdin);
|
||
#endif
|
||
|
||
cin >> n; // 4
|
||
string s; // abccddadca
|
||
cin >> s;
|
||
// 先把字符串存入char[][]
|
||
int idx = 0;
|
||
for (int i = 1; i <= n; i++) // n行
|
||
for (int j = 1; j <= i; j++) // i列
|
||
a[i][j] = s[idx++];
|
||
|
||
// 把所有序号记录下来
|
||
for (int i = 1; i <= n; i++)
|
||
for (int j = 1; j <= i; j++)
|
||
q.push_back({i, j, a[i][j]});
|
||
|
||
vector<char> res;
|
||
// 在q数组中，选择任意三个，计算两两间距离是不是相等
|
||
for (int i = 0; i < q.size(); i++)
|
||
for (int j = i + 1; j < q.size(); j++)
|
||
for (int k = j + 1; k < q.size(); k++)
|
||
if (check(q[i], q[j], q[k])) res.push_back(q[i].c);
|
||
|
||
if (res.size() == 0)
|
||
cout << "No Solution" << endl;
|
||
else {
|
||
sort(res.begin(), res.end());
|
||
for (char x : res) cout << x;
|
||
}
|
||
return 0;
|
||
} |