"водопровод"

Тема в разделе "C/C++/C#", создана пользователем crewww, 25 дек 2011.

  1. crewww

    crewww Гость

    вот условие задачи
    Город Восточный постоянно страдает от недостатка воды. Для устранения этой проблемы была построена новая водопроводная труба. Строительство трубы началось с обоих концов одновременно, и спустя некоторое время половины соединились. Ну, почти. Первая половина трубы заканчивалась в точке (x1, y1), а вторая - в точке (x2, y2).
    К сожалению, осталось лишь несколько отрезков трубы различной длины. Более того, из-за специфики местной технологии трубы могут быть проложены только в направлении с севера на юг или с востока на запад и соединяются, образуя или прямую, или угол 90 градусов. Требуется, зная длины отрезков труб L1, L2, ..., LK и количество отрезков каждой длины C1, C2, ..., CK, сконструировать трубу, соединяющую две заданные точки, или определить, что это невозможно.
    Ограничения: 1 <= K <= 4, 1 <= x1, y1, x2, y2, Li <= 1000, 1 <= Ci <= 10, все числа целые, время 3 с.
    Ввод из файла wpipe.in. В первой строке находятся числа x1, y1, x2, y2, K, затем 2K чисел: L1, L2, ..., LK, C1, C2, ..., CK.
    Вывод в файл wpipe.out. Вывести одно число - минимальное количество нужных отрезков труб или -1, если соединение невозможно.
    в книге нашел алгоритм
    Безымянный.jpg
    Безымянный.png
    но как реализовать пока не представляю
    если вам не трудно то не могли бы вы мне дать идею, мне важен не сам готовый код, а именно понять как реализовать алгоритм вот с этим беда
     
  2. crewww

    crewww Гость

    #include <iostream>
    #include <fstream>
    using namespace std;
    void main()
    {ifstream wpipein; ofstream wpipeout;
    int c[4],l[4]; int x1,y1,x2,y2,i,j,s=0,t=0,m;
    int k;
    wpipein.open("wpipein.txt"); wpipeout.open("wpipeout.txt");
    wpipein>>x1>>y1>>x2>>y2>>k;
    for (i=0; i<k; i++)
    wpipein>>c>>l;
    for (i=0;i<k; i++)
    for (j=0;j<k;j++)
    {if ((abs(x1-x2)==s+c*l)&&(abs(y1-y2)==t+c[j]*l[j])&&(c[k]>=c+c[j]))
    {s=c*l; t=c[j]*l[j];
    if ((abs(x1-x2)%l[k]==0)&&(abs(y1-y2)%l[k]==0))
    {m=abs(x1-x2)/l[k]+abs(y1-y2)/l[k];
    if (m<=c[k]) wpipeout<<m; else wpipeout<<-1;
    }}}}
    написал код но он не работает правильно если конечно вообще работает
     

Поделиться этой страницей