三角形的优雅值(map和哈希表)

给你 n 个三角形,每个三角形有一个优雅值,
然后给出一个询问,每次询问一个三角形,
求与询问的三角形,相似的三角形中的优雅值最大是多少。
★数据输入
第一行输入包括 n 一个数字,
接下来 n 行,每行四个整数数字
a,b,c,val 表示三条边,以及优美值
之后输入一个数字 m
之后 m 行,每行三个数字 a,b,c,表示询问的三角形。
★数据输出
输出 m 行,如果查询的三角形不在给定的 n 个中,输出”Sorry”,否则输出三角
形的优美值

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 范围内

知识1:相似三角形的判断: 将其都化成最小的整数相似三角形，如6,8,10化为3，4，5

解法一：用map，搜索比hash表慢

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <map>
#include <string>
using namespace std;
map<__int64,int> mp;
int gcd(int a,int b)
{
    if(b==)    return a;
    else        return gcd(b,a%b);
}
int max(int a,int b)
{
    if(a>b)    return a;
    else    return b;
}
int main()
{
    int n,m,a[],val,i,t,k,hash;
    scanf("%d",&n);
    mp.clear();
    for(i=;i<n;i++)
    {
        scanf("%d %d %d %d",&a[],&a[],&a[],&val);
        k = gcd(a[],gcd(a[],a[]));
        a[]/=k;a[]/=k;a[]/=k;
        sort(a,a+);
        hash = (a[]* +a[])* + a[];
        if(mp.find(hash) != mp.end())
                mp[hash] = max(mp[hash],val);
        else
            mp[hash] = val;
    }
    scanf("%d",&m);
    for(i=;i<m;i++)
    {
        scanf("%d %d %d",&a[],&a[],&a[]);
        k = gcd(a[],gcd(a[],a[]));
        a[]/=k;a[]/=k;a[]/=k;
        sort(a,a+);
        hash = (a[]* +a[])* + a[];
        if(mp.find(hash) != mp.end())
            printf("%d\n",mp[hash]);
        else
            printf("Sorry\n");
    }
    return ;
}

解法2：用hash表做

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <map>
#include <string>
using namespace std;
struct Node {
    __int64 hash;
    int val;
}tri[];

int gcd(int a,int b)
{
     return b ? gcd(b, a % b) : a;
}
bool cmp(Node a, Node b)
{
    if (a.hash != b.hash) return a.hash < b.hash;
    else return a.val > b.val;    //hash值相等时按val值排序
}
int Lower_bound(Node *array, int size, int key)
{
    int first = , middle;
    int half, len;
    len = size;

    while(len > ) {
        half = len >> ;
        middle = first + half;
        if(tri[middle].hash < key) {
            first = middle + ;
            len = len-half-;       //在右边子序列中查找
        }
        else
            len = half;            //在左边子序列（包含middle）中查找
    }
    return first;
}
int main()
{
    int n,m,a[],val,i,t,k;
    __int64 hash;
    scanf("%d",&n);
    //mp.clear();
    for(i=;i<n;i++)
    {
        scanf("%d %d %d %d",&a[],&a[],&a[],&val);
        k = gcd(a[],gcd(a[],a[]));
        a[]/=k;a[]/=k;a[]/=k;
        sort(a,a+);
        hash = (a[]* +a[])* + a[];
        tri[i].hash = hash;
        tri[i].val = val;
    }
    sort(tri,tri+n,cmp);
    scanf("%d",&m);
    for(i=;i<m;i++)
    {
        scanf("%d %d %d",&a[],&a[],&a[]);
        k = gcd(a[],gcd(a[],a[]));
        a[]/=k;a[]/=k;a[]/=k;
        sort(a,a+);
        hash = (a[]* +a[])* + a[];
        int pos = Lower_bound(tri,n,hash);
        if (pos == n || tri[pos].hash != hash) puts("Sorry");
        else printf("%d\n", tri[pos].val);
    }
    return ;
}