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

问题描述

给你 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

 #include <stdio.h>

 #include <stdlib.h>

 #include <iostream>

 using namespace std;

 #define MAXN 100001

 struct Triangle

 {

     Triangle(double &_rate12, double &_rate13, int &_weight)

         :rate12(_rate12), rate13(_rate13), weight(_weight),next(NULL) {}

     double rate12;

     double rate13;

     int weight;

     Triangle *next;

 };

 Triangle *arr[MAXN];

 inline int calcHash(int &a, int &b, int &c)

 {

     double f = (1.0*a / b + 1.0*a / c);

     __int64 i64 = f * ;

     return i64 % MAXN;

 }

 inline void sort3(int &a,int &b,int &c)//1 2 3 (from min to max)

 {

     if (a > b) { a ^= b; b ^= a; a ^= b; }

     if (b > c) { c ^= b; b ^= c; c ^= b; }

     if (a > b) { a ^= b; b ^= a; a ^= b; }

 }

 int main()

 {

     //freopen("test.txt", "r", stdin);

     //freopen("out.txt","w",stdout);

     int i, j;

     int n, m;

     int a, b, c, w;

     scanf("%d", &n);

     for (i = ; i < n; i++)

     {

         scanf("%d %d %d %d", &a, &b, &c, &w);

         sort3(a, b, c);

         int index = calcHash(a, b, c);

         double rate12 = 1.0*a / b;

         double rate13 = 1.0*a / c;

         Triangle *p = arr[index];

         if (p==NULL)

         {

             arr[index] = new Triangle(rate12, rate13, w);

         }

         else

         {

             Triangle * tail = p;

             bool found = false;

             while (p)

             {

                 if (rate12 == p->rate12 && rate13 == p->rate13)

                 {

                     if(w > p->weight)

                         p->weight = w;

                     found = true;

                     break;

                 }

                 else

                 {

                     tail = p;

                     p = p->next;

                 }

             }

             if (!found)

             {

                 tail->next = new Triangle(rate12, rate13, w);

             }

         }

     }

     scanf("%d", &m);

     for (i = ; i < m; i++)

     {

         scanf("%d %d %d", &a, &b, &c);

         sort3(a, b, c);

         int index = calcHash(a, b, c);

         double rate12 = 1.0*a / b;

         double rate13 = 1.0*a / c;

         Triangle *p = arr[index];

         bool found = false;

         while (p)

         {

             if (rate12 == p->rate12 && rate13 == p->rate13)

             {

                 found = true;

                 printf("%d\n", p->weight);

                 break;

             }

             else

                 p = p->next;

         }

         if (!found) printf("Sorry\n");

     }

     return ;

 }

巴特西

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

最新文章

热门文章