Задание "Юный поджигатель"

Ответить

Код подтверждения
Введите код в точности так, как вы его видите. Регистр символов не имеет значения.
BBCode ВКЛЮЧЁН
[img] ВКЛЮЧЁН
[flash] ОТКЛЮЧЕН
[url] ВКЛЮЧЁН
Смайлики ОТКЛЮЧЕНЫ
Обзор темы
   

Развернуть Обзор темы:Задание "Юный поджигатель"

Re: Задание "Юный поджигатель"

MitZ »23 апр 2021, 15:17

В общем, визуализация подождёт пока.

Но почему-то у меня координаты не сходятся с желаемым.

Нужно сделать так, чтобы результат был вот таким:
Example
3
1 1 1 2 10
1 2 2 2 10
1 1 2 2 50

Result
2 2
35.00

Задание "Юный поджигатель"

MitZ »19 апр 2021, 20:06

Здравствуйте! Вот есть такое задание:

Имя входного файла: f.in.
Имя выходного файла: f.out.

На клеточном поле введена система координат так, что центр координат находится в точке пересечения линий сетки и оси направлены вдоль линий сетки.
На этом поле выложили связную фигуру, состоящую из спичек. Использовались спички двух типов:
• Спички длины 1 выкладывались по сторонам клеток.
• Спички длины sqrt 2 ("квадратный корень из 2") выкладывались по диагоналям клеток.
Ребенок хочет сжечь фигуру. При этом он может поджечь ее в одной точке, имеющей целочисленные координаты (например, в точке A на рисунке поджигать фигуру нельзя, а в точках B и C — можно).
Известно, что огонь распространяется вдоль спички равномерно (но по каждой спичке — со своей скоростью). Спичка может гореть в нескольких местах (например, когда она загорается с двух концов; или когда в середине диагональной спички огонь перекидывается с одной спички на другую — огонь расползается по вновь подожженной спичке в обе стороны).
Напишите программу, которая определит, в какой точке нужно поджечь фигуру, чтобы она сгорела за минимальное время.

Формат входных данных
Во входном файле записано сначала число N — количество спичек (1N40). Затем идет N пятерок чисел вида X1, Y1, X2, Y2, T, задающих координаты концов спички и время ее сгорания при условии, что она будет подожжена с одного конца (гарантируется, что каждая спичка имеет длину 1 или sqrt 2 ("квадратный корень из 2"), все спички образуют связную фигуру, и положение никаких двух спичек не совпадает). Все координаты — целые числа, по модулю не превышающие 200, время сгорания — натуральное число, не превышающее 10^7 ("10 в степени 7").

Формат выходных данных
Выведите координаты целочисленной точки, в которой нужно поджечь фигуру, чтобы она сгорела за наименьшее время, а затем время, за которое в этом случае фигура сгорит. Время должно быть выведено с точностью не менее 2-х знаков после десятичной точки. Если решений несколько, выведите любое из них.

Пример
f.in
3
1 1 1 2 10
1 2 2 2 10
1 1 2 2 50

f.out
2 2
35.00

Код программы:

Код: Выделить всё

#include <bits/stdc++.h>
 
#define pb push_back
#define ll long long
#define ld long double
#define ull unsigned long long
#define F first
#define S second
#define uint unsigned int
#define forn(i, n) for (int i = 0; i < n; i++)
 
using namespace std;
 
ld g[150][150];
int main()
{
 
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
//    freopen("12.in", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int n;
    cin >> n;
    vector <pair <int, int>> a;
    set <pair <int, int>> st;
    forn(i, 150)
        forn(j, 150)
            if (i != j) g[i][j] = 1e10;
                else g[i][j] = 0;
    vector <pair <ld, pair <int, int>>> sp;
    forn(i, n)
    {
        int x1, y1, x2, y2;
        ld q;
        cin >> x1 >> y1 >> x2 >> y2 >> q;
        x1 *= 2;
        x2 *= 2;
        y1 *= 2;
        y2 *= 2;
        int xt = (x1 + x2) / 2;
        int yt = (y1 + y2) / 2;
        if (st.find({xt, yt}) == st.end()) a.pb({xt, yt});
        if (st.find({x1, y1}) == st.end()) a.pb({x1, y1});
        if (st.find({x2, y2}) == st.end()) a.pb({x2, y2});
        int t, t1, t2;
        forn(j, int(a.size()))
            if (a[j] == make_pair(x1, y1)) {t1 = j; break;}
        forn(j, int(a.size()))
            if (a[j] == make_pair(x2, y2)) {t2 = j; break;}
        forn(j, int(a.size()))
            if (a[j] == make_pair(xt, yt)) {t = j; break;}
        st.insert({x1, y1});
        st.insert({x2, y2});
        st.insert({xt, yt});
        g[t1][t] = q / 2;
        g[t][t1] = q / 2;
        g[t][t2] = q / 2;
        g[t2][t] = q / 2;
        sp.pb({q / 2, {t1, t}});
        sp.pb({q / 2, {t, t2}});
    }
 
    forn(c, int(a.size()))
        forn(i, int(a.size()))
            forn(j, int(a.size()))
        if (g[i][j] > g[i][c] + g[c][j])
            g[i][j] = g[i][c] + g[c][j];
	ld mx = 1e9;
	int vv;
    for(int j = 0; j <  int(a.size()); j++)
    {
    	int v = j;
    	if (a[v].F % 2 != 0 || a[v].S % 2 != 0) continue;
    	ld mn = 0;
    for(int i = 0; i <  int(sp.size()); i++)
    {
        ld time = sp[i].F;
        ld t1 = g[v][sp[i].S.F];
        ld t2 = g[v][sp[i].S.S];
        if (t2 > t1) swap(t1, t2);
        ld now = min(t1 - t2, time);
        time -= now;
        now += time / 2;
        now += t2;
        if (now > mn) mn = now;
    }
		if (mn < mx) {mx = mn; vv = j;}
 
    }
    cout << a[vv].F / 2 << ' ' << a[vv].S / 2 << '\n' << fixed << setprecision(5) << mx;
    return 0;
}
Хотелось бы понять, как реализовать данную программу визуально, т.е. её отобразить на обычной форме проекта в C++ Builder (можно даже 6-ю версию использовать для этого).

Вернуться к началу