ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1588. Jamaica

WA2
Posted by AleshinAndrei 19 Aug 2020 23:26
How do you think what's the input-data in test-2? I did tested my program around 10 times :) but i didn't find mistake((

UPD: N = 1 )))
you mustn't test borders-cases in input data. You must check your algorithm.
In this case i have "out of range" (because v_arr has length = 0, but in this program i don't check it and i address to zero index).
If check border-case this algorithm is working

My program:
@@
#include <iostream>
#include <cmath>

struct Point {
    int64_t x;
    int64_t y;
};

struct Vector {
    double r;
    double angle;
};

int cmp(const void *a, const void *b){
    Vector* v1 = (Vector*)a;
    Vector* v2 = (Vector*)b;
    double ans1 = ((v1->angle) - (v2->angle));
    if (ans1 < 0){
        return -1;
    } else if (ans1 > 0){
        return 1;
    }
    double ans2 = ((v1->r) - (v2->r));
    if (ans2 < 0){
        return -1;
    } else if (ans2 > 0){
        return 1;
    }
    return 0;
}

int main()
{
    int N;
    std::cin >> N;
    Point p_arr[N];
    Vector v_arr[N-1];
    double dist = 0;
    int64_t dx, dy;
    for (int i = 0; i < N; ++i){
        std::cin >> p_arr[i].x >> p_arr[i].y;
    }
    for (int i = 0; i < N; ++i){
        for (int j = 0; j < i; ++j){
            dx = p_arr[j].x - p_arr[i].x;
            dy = p_arr[j].y - p_arr[i].y;
            v_arr[j].r = sqrt(dx*dx + dy*dy);
            v_arr[j].angle = atan2(dy, dx);
        }
        for (int j = i+1; j < N; ++j){
            dx = p_arr[j].x - p_arr[i].x;
            dy = p_arr[j].y - p_arr[i].y;
            v_arr[j-1].r = sqrt(dx*dx + dy*dy);
            v_arr[j-1].angle = atan2(dy, dx);
        }
        qsort(v_arr, N-1, sizeof(Vector), cmp);
        for (int j = N-2; j > 0; --j){
            v_arr[j].angle -= v_arr[j-1].angle;
        }
        dist += v_arr[0].r;
        for (int j = 1; j < N-1; ++j){
            if (v_arr[j].angle != 0){
                dist += v_arr[j].r;
            }
        }
    }
    printf("%.0f", (dist / 2));
}
@@




Edited by author 20.08.2020 00:55