알고리즘 과 데이터 구조 9.2

★ 실험 의뢰
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;

데이터 의 저장 \ # define MAXN 100001 / / 상황 에 따라 MAXN 길 이 를 정 하 는 포인터 배열 입 니 다. 모든 요 소 는 하나의 링크 헤더 가 삼각형 으로 구 한 해시 값 은 바로 배열 의 아래 표 입 니 다. (주의, 비슷 하지 않 은 삼각형 은 같은 해시 값 이 있 을 수 있 습 니 다) 대응 하 는 링크 를 옮 겨 다 니 며 변 비례 비례 비례 비례 가 현재 와 같 음 (비슷 함) 을 찾 으 면한편, 가중치 가 비교적 작은 것 은 현재 의 비교적 큰 가중치 로 교체 합 니 다. 만약 에 변 비례 비례 비례 비례 를 찾 으 면 현재 의 비례 와 같 고 가중치 가 현재 보다 크 며 break 를 제거 합 니 다. 현재 값 을 저장 하지 않 고 찾 지 못 하면 링크 뒤에 검색 동 리 를 추가 합 니 다. 해시 값 을 계산 하여 링크 ★ Code

를 옮 겨 다 닙 니 다.

 
            #include
#include

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;
}

        

다음으로 전송:https://www.cnblogs.com/031602523liu/p/7901078.html