数据结构_相似三角形优雅值

数据结构_相似三角形优雅值_sjx

问题描述

给你 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.0*a/b，1.0*a/c，若两个三角形对应比值相等，那么这两个三角形相似

　　哈希值的计算

　　　　极限的数据会出现类似 1.0*100000/99999 与1.0*99999/99998这样的情况，要精确的小数点后10为才能比较

　　　　以下是我的哈希值求法（或许有更优的做法，能散的更开，更平均，求告知）

　　　　　　　double f = (1.0*a / b + 1.0*a / c);
　　　　　　__int64 i64 = f * 1000000000;
　　　　　　return i64 % MAXN;

　　数据的存储

　　　　#define MAXN 100001 //开多少视情况而定

　　　　开MAXN长度的指针数组，每个元素都是一个链表表头

　　　　用三角形求出的哈希值就是数组的下标，（注意，不相似的三角形可能有相同的哈希值）

　　　　遍历对应链表，若找到边比例比例与当前的相等（相似），而权值比较小的，就用当前的较大权值替换之

　　　　　　　　　　若找到边比例比例与当前的相等，而权值比当前大，break掉，不存储当前值

　　　　　　　　　　若未找到，则在链表后新加一个

　　查找同理，算哈希值，遍历链表

　　试着用map写了一下，最后3个点RE。。。。。。

　　还是不能偷懒啊

code

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <iostream>
  4 using namespace std;
  5 
  6 #define MAXN 100001
  7 
  8 struct Triangle
  9 {
 10     Triangle(double &_rate12, double &_rate13, int &_weight)
 11         :rate12(_rate12), rate13(_rate13), weight(_weight),next(NULL) {}
 12     double rate12;
 13     double rate13;
 14     int weight;
 15     Triangle *next;
 16 };
 17 
 18 Triangle *arr[MAXN];
 19 
 20 inline int calcHash(int &a, int &b, int &c)
 21 {
 22     double f = (1.0*a / b + 1.0*a / c);
 23     __int64 i64 = f * 1000000000;
 24     return i64 % MAXN;
 25 }
 26 
 27 inline void sort3(int &a,int &b,int &c)//1 2 3 (from min to max)
 28 {
 29     if (a > b) { a ^= b; b ^= a; a ^= b; }
 30     if (b > c) { c ^= b; b ^= c; c ^= b; }
 31     if (a > b) { a ^= b; b ^= a; a ^= b; }
 32 }
 33 
 34 int main()
 35 {
 36     //freopen("test.txt", "r", stdin);
 37     //freopen("out.txt","w",stdout);
 38     int i, j;
 39     int n, m;
 40     int a, b, c, w;
 41     scanf("%d", &n);
 42 
 43     for (i = 0; i < n; i++)
 44     {
 45         scanf("%d %d %d %d", &a, &b, &c, &w);
 46         sort3(a, b, c);
 47         int index = calcHash(a, b, c);
 48         double rate12 = 1.0*a / b;
 49         double rate13 = 1.0*a / c;
 50         Triangle *p = arr[index];
 51         if (p==NULL)
 52         {
 53             arr[index] = new Triangle(rate12, rate13, w);
 54         }
 55         else
 56         {
 57             Triangle * tail = p;
 58             bool found = false;
 59             while (p)
 60             {
 61                 if (rate12 == p->rate12 && rate13 == p->rate13)
 62                 {
 63                     if(w > p->weight)
 64                         p->weight = w;
 65                     found = true;
 66                     break;
 67                 }
 68                 else
 69                 {
 70                     tail = p;
 71                     p = p->next;
 72                 }
 73             }
 74             if (!found)
 75             {
 76                 tail->next = new Triangle(rate12, rate13, w);
 77             }
 78         }
 79 
 80     }
 81 
 82     scanf("%d", &m);
 83     for (i = 0; i < m; i++)
 84     {
 85         scanf("%d %d %d", &a, &b, &c);
 86         sort3(a, b, c);
 87         int index = calcHash(a, b, c);
 88         double rate12 = 1.0*a / b;
 89         double rate13 = 1.0*a / c;
 90         Triangle *p = arr[index];
 91         bool found = false;
 92         while (p)
 93         {
 94             if (rate12 == p->rate12 && rate13 == p->rate13)
 95             {
 96                 found = true;
 97                 printf("%d
", p->weight);
 98                 break;
 99             }
100             else
101                 p = p->next;
102         }
103         if (!found) printf("Sorry
");
104     }
105 
106     return 0;
107 }