Untitled

 avatar
unknown
c_cpp
3 years ago
4.3 kB
2
Indexable
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cmath>
#include <list>

struct Man {
    double x {0};
    double y {0};
    double velocity {0};
};

struct Guide : Man {

};

struct Senior : Man {
    int number {0};
    double pathAngle {0};
    double timeToReturn {0};
};

double calculateDistance(double x1, double y1, double x2, double y2) {
    double dx = x2 - x1;
    double dy = y2 - y1;
    return sqrt(dx*dx + dy*dy);
}

double calculateGuidePathAngle(const Senior &senior, const Guide &guide, double viewingAngle) {
    return viewingAngle - asin((senior.velocity / guide.velocity) * sin(viewingAngle - senior.pathAngle));
}

double calculateTimeToCatchSenior(const Senior &senior, const Guide &guide) {
    double distance = calculateDistance(senior.x, senior.y, guide.x, guide.y);
    double viewingAngle = atan2(senior.y - guide.y, senior.x - guide.x);
    double guidePathAngle = calculateGuidePathAngle(senior, guide, viewingAngle);

    return distance / (guide.velocity * cos(viewingAngle - guidePathAngle) - senior.velocity * cos(viewingAngle - senior.pathAngle));
}

void recalculateTimeToReturnOnBus(std::list<Senior> &seniorList, double timePassed) {
    for(auto &senior : seniorList) {
        if(senior.timeToReturn > timePassed) {
            senior.timeToReturn -= timePassed;
        }
        else {
            senior.timeToReturn = 0;
        }
    }
}

void recalculateSeniorCoordinates(std::list<Senior> &seniorList, double timePassed) {
    for(auto &senior : seniorList) {
        double distance = senior.velocity * timePassed;
        senior.x += distance * cos(senior.pathAngle);
        senior.y += distance * sin(senior.pathAngle);
    }
}

int calculateTimeToReturnSeniors(const std::list<Senior> &seniorList, const Guide &guide) {

    std::list<Senior> catchedSeniors;
    double minimumTimeToReturnAll = std::numeric_limits<double>::max();

    auto seniorListPermutation = seniorList;

    auto idComparation = [](const Senior &first, const Senior &second) {
        return first.number < second.number;
    };

    auto returnTimeCompation = [](const Senior &first, const Senior &second) {
        return first.timeToReturn < second.timeToReturn;
    };

    do {
        double timePassed = 0.0;
        auto seniorListPermutationOnIteration = seniorListPermutation;
        auto guideOnIteration = guide;
        while(!seniorListPermutationOnIteration.empty()) {
            auto &senior = seniorListPermutationOnIteration.front();
            double timeToCatch = calculateTimeToCatchSenior(senior, guide);

            recalculateTimeToReturnOnBus(catchedSeniors, timeToCatch);
            recalculateSeniorCoordinates(seniorListPermutationOnIteration, timeToCatch);

            guideOnIteration.x = senior.x;
            guideOnIteration.y = senior.y;

            senior.timeToReturn = calculateDistance(senior.x, senior.y, 0, 0) / senior.velocity;

            catchedSeniors.splice(catchedSeniors.end(), seniorListPermutationOnIteration, seniorListPermutationOnIteration.begin());
            timePassed += timeToCatch;
        }

        auto maxReturnTimeSenior = *std::max_element(catchedSeniors.begin(), catchedSeniors.end(), returnTimeCompation);
        double totalTime = maxReturnTimeSenior.timeToReturn + timePassed;
        minimumTimeToReturnAll = std::min(totalTime, minimumTimeToReturnAll);

        catchedSeniors.clear();

    } while(std::next_permutation(seniorListPermutation.begin(), seniorListPermutation.end(), idComparation));

    return std::round(minimumTimeToReturnAll);
}


int main() {

    using std::cin;

    std::list<Senior> seniorList;

    while(1) {

        int seniorCount = 0;
        cin >> seniorCount;
        if(!seniorCount)
            break;
        Guide guide;
        cin >> guide.velocity;
        int seniorNumber = 0;
        while(seniorCount) {
            Senior senior;
            cin >> senior.x >> senior.y >> senior.velocity >> senior.pathAngle;
            senior.number = seniorNumber;
            seniorNumber++;
            seniorCount--;
            seniorList.push_back(senior);
        }
        int timeToReturnSeniors = calculateTimeToReturnSeniors(seniorList, guide);
        std::cout << timeToReturnSeniors << std::endl;
        seniorList.clear();
    }
    return 0;
}