★实验任务
给你 n 个三角形,每个三角形有一个优雅值,
然后给出一个询问,每次询问一个三角形,
求与询问的三角形,相似的三角形中的优雅值最大是多少。
★数据输入
第一行输入包括 n 一个数字,
接下来 n 行,每行四个整数数字
a,b,c,val 表示三条边,以及优美值
之后输入一个数字 m
之后 m 行,每行三个数字 a,b,c,表示询问的三角形。
★数据输出
输出 m 行,如果查询的三角形不在给定的 n 个中,输出”Sorry”,否则输出三角 形的优美值
| 输入示例 | 输出示例 |
|---|---|
| 3 3 5 4 10 6 8 10 20 2 3 4 5 3 3 4 5 4 5 6 2 3 4 |
20 Sorry 5 |
★提示
给出的三条边无序,且保证可以构成三角形
40%数据 不需要考虑相似条件
70%的数据 1<=n,m<=1,000 1<=a,b,c<=1,000
100%的数据 1<=n<=200,000 1<=m<=500,000 a,b,c(1<=a,b,c<=100,000) val 在 int 范围内
★思路
- 对三角形相似的判断
对三角形的三边abc排序，a最小，c最大
任取两边相除得到两个比值 1.0a/b，1.0a/c，若两个三角形对应比值相等，那么这两个三角形相似 - 哈希值的计算
极限的数据会出现类似 1.0100000/99999 与1.099999/99998这样的情况，要精确的小数点后10为才能比较
以下是我的哈希值求法（或许有更优的做法，能散的更开，更平均，求告知）
double f = (1.0*a / b + 1.0*a / c);
__int64 i64 = f * 1000000000;
return i64 % MAXN;<br>
- 数据的存储
#define MAXN 100001 //开多少视情况而定
开MAXN长度的指针数组，每个元素都是一个链表表头
用三角形求出的哈希值就是数组的下标，（注意，不相似的三角形可能有相同的哈希值）
遍历对应链表，若找到边比例比例与当前的相等（相似），而权值比较小的，就用当前的较大权值替换之
若找到边比例比例与当前的相等，而权值比当前大，break掉，不存储当前值
若未找到，则在链表后新加一个
查找同理，算哈希值，遍历链表
★Code
#include<stdio.h>
#include<stdlib.h>
typedef struct trangle
{
double scale1, scale2;
int data;
struct trangle *next;
}tran;
tran *hash_[100005];
void in_hash(int str[], int _data)
{
int i;
double t;
t = (str[1] * 1.0) / (str[2] * 1.0) + (str[0] * 1.0) / (str[1] * 1.0);
//t = 1.0*str[1]*str[0]/str[2]/str[2];
__int64 i64 = t * 1000000000;
int temp = i64 % 100001;
tran *p = (tran*)malloc(sizeof(tran));
int w = 0;
tran *q = hash_[temp];
while (q)
{
if ((str[1] * 1.0) / (str[0] * 1.0) == q->scale1 && (str[2] * 1.0) / (str[1] * 1.0) == q->scale2)
{
if (_data > q->data)
q->data = _data;
w = 1;
break;
}
q = q->next;
}
if (w == 0)
{
p->data = _data;
p->scale1 = (str[1] * 1.0) / (str[0] * 1.0);
p->scale2 = (str[2] * 1.0) / (str[1] * 1.0);
p->next = hash_[temp];
hash_[temp] = p;
}
}
void tranglesort(int str[])
{
int i, j, t;
for (i = 0; i < 2; i++)
{
for (j = i + 1; j < 3; j++)
{
if (str[i] > str[j])
{
t = str[i];
str[i] = str[j];
str[j] = t;
}
}
}
}
void search_hash_(int str[])
{
int i;
double temp;
temp = (str[1] * 1.0) / (str[2] * 1.0) + (str[0] * 1.0) / (str[1] * 1.0);
__int64 i64 = temp * 1000000000;
int ans = i64 % 100001;
tran *p = hash_[ans];
while (p)
{
if ((str[1] * 1.0) / (str[0] * 1.0) == p->scale1 && (str[2] * 1.0) / (str[1] * 1.0) == p->scale2)
{
printf("%d", p->data);
return;
}
else
p = p->next;
}
printf("Sorry");
}
int main()
{
int dat[3] = { 0 }, i, j, n, m, grace;
scanf("%d", &n);
for (i = 0; i < n; i++)
{
for (j = 0; j < 3; j++)
scanf("%d", &dat[j]);
scanf("%d", &grace);
tranglesort(dat);
in_hash(dat, grace);
}
scanf("%d", &m);
for (i = 0; i < m; i++)
{
for (j = 0; j < 3; j++)
scanf("%d", &dat[j]);
tranglesort(dat);
search_hash_(dat);
if (i != m)
printf("
");
}
return 0;
}