Big Circle JBOI 2014

Za ovaa zadaca nemav nekoja ideja, pa prvo ja iskucav so brute-force , no bidejki moze da ima 10^5 koordinati, so brute-force slozenosta bi bila (10^5)^2, a toa e povekje operacii, od limitot za 1 sekunda. Po malku razmisluvanje , dojdov do zaklucok deka samo treba da gi sortiram, i so eden ciklus da baram minimum, ova pominuva na 3 sluchaevi, a na drugite dava pogresen rezultat. Mozebi greskata mi e vo toa deka ne treba da gi sortiram po prviot , tuku po vtoriot.
Eve go kodot:

Fala odnapred

Edit: Probav so sortiranje po vtor element, taka pominuva na 4 test cases.

This message was edited 1 time. Last update was at 25/02/2019 21:05:40

Ajde nekoj hint at least

BATIR wrote:Ajde nekoj pomos, ili hint at least

Не мора само една (следна) точка, можеш да разгледаш повеќе блиски. Вака нешто.

This message was edited 1 time. Last update was at 24/02/2019 22:27:19

Moze malku podetalno da mi objasnis shto pravis vo 25 red i 26?
Inaku fala mnogu

BATIR wrote:Moze malku podetalno da mi objasnis shto pravis vo 25 red i 26?
Inaku fala mnogu

Ако i=5, наместо да гледаме само растојание до 6-тата точка, може да гледаме до 6, 7, 8, 9, 10, ... итн (ако n е помало, можеме да продолжиме од 0, 1, 2, 3, ... тоа е j%n)
Идејата ми е да се искористи фактот што временскиот лимит ни дозволува да разгледаме повеќе точки.

Tnx

This message was edited 1 time. Last update was at 10/06/2019 12:26:15

solution c++:

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
 
#define eps 0.000001
 
struct point {
    double x,y;
} points[333555];
 
double dist(point p1, point p2) {
    return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}
 
bool cmp(point p1, point p2) {
 
    double u1,u2;
 
    if (fabs(p1.y - points[0].y) < eps) return false;
    if (fabs(p2.y - points[0].y) < eps) return true;
 
    u1 = (p1.x - points[0].x) / (p1.y - points[0].y);
    u2 = (p2.x - points[0].x) / (p2.y - points[0].y);
 
    return (u1 < u2);
}
 
int main() {
 
    int n,p,i;
    double d,res;
    point tmp;
 
    scanf("%d", &n);
 
    p = 0;
    for(i=0; i<n; i++) {
        scanf("%lf%lf", &points[i].x, &points[i].y);
        if (points[i].y < points[p].y || (fabs(points[i].y - points[p].y) < eps && points[i].x < points[p].x) ) {
            p = i;
        }
    }
 
    tmp = points[0]; points[0] = points[p]; points[p] = tmp;
 
    sort(points+1,points+n,cmp);
 
    res = dist(points[0], points[n-1]);
 
    for(i=1; i<n; i++) {
        d = dist(points[i], points[i-1]);
        if (d < res) res = d;
    }
 
    printf("%.2lf\n", res);
 
    return 0;
}