/**Problem H
Lane Switching
The Autonomous Car Manufacturer (ACM) needs to design algorithms to
control their cars. One particular problem is lane switching—if the
car needs to switch lanes, it wants to do so in the safest manner.
Initially the car is in the leftmost lane, and the car needs to switch
to the rightmost lane. The car has a variety of sensors and can obtain
the locations of all cars in a section of the highway. When the car needs
to switch lanes, it takes a snapshot of the sensor readings and design a
plan to switch lanes based on the snapshot. The sensors have limited range.
All sensor readings will be distances from the start of the sensor range.
For safety reason, the areas outside of the sensor range are assumed to
be occupied by cars.
You may assume that all other cars are travelling at exactly the speed limit.
However, the ACM would like to set itself apart by producing cars that may
drive at any speed regardless of the speed limit, as long as it does not hit
any other car. For safety reasons, a lane switch is always done while driving
at the speed limit.
When a lane switch occurs, the destination must have unoccupied space for the
car to move into (a perfect fit is allowed). We define the safety factor of
the plan as the closest distance to any car while executing the plan. We are only
concerned about cars in the same lane, and will ignore distances between cars in
different lanes. Obviously, the ACM wants its cars to choose a plan that has the
highest safety factor.
Input
The first line of input contains three integers NN (2≤N≤100), M (M≥1),
R (1≤R≤1000000) indicating the number of lanes, the number of cars on the road,
and the sensor range. The next M lines describe each car with three integers:
the lane number (between 0 and N−1, inclusive), the length of the car (positive),
and the distance from the start of the sensor range to the back of the car.
The distance is non-negative and at most R. The first car given is the ACM car.
Lane 0 is the leftmost lane, and lane N−1 is the rightmost lane.
There are at most 100 cars in each lane. No two cars will overlap although they
may touch bumper-to-bumper.
Output
If the ACM car can switch from lane 0 to lane N−1, print a single number indicating
the maximum achievable safety factor. Otherwise, print Impossible. Your answer will
be considered correct if its absolute error does not exceed 10^−5.**/
#include
#include
#include
using namespace std;
struct Link;
struct Node {
vector vL;
};
struct Link {
Node* N;
float w;
};
struct Car {
int lane;
int length;
int lowest;
int highest= lowest+length;
Car(int ln, int len, int low) :
lane(ln), length(len), lowest(low) {}
void print() {
cout << lane << " " << length << " " << lowest << " " << highest << endl;
}
};
struct Space {
int lane;
int start;
int stop;
int length = stop-start;
Space(int l, int str, int stp) :
lane(l), start(str), stop(stp) {}
};
vector > sortCarsByLanes(vector& vc, int numberOfCars, int numberOfLanes) {
vector > lanes(numberOfLanes);
for(Car c: vc) {
cout << "\nc.lane = " << c.lane;
lanes[c.lane].push_back(c);
}
return lanes;
}
void print_spaces(const vector >& vvi) {
for(int i = 0; i < vvi.size(); ++i) {
for(int j = 0; j < vvi[i].size(); ++j)
cout << vvi[i][j] << " ";
cout << endl;
}
}
int main() {
ifstream read("laneCars.txt");
int numberOfLanes, numberOfCars, lengthOfSensor;
read >> numberOfLanes >> numberOfCars >> lengthOfSensor;
///vector vc; //contains all cars
vector vs;
int low, lane, length;
read >> lane >> length >> low;
Car acmCar(lane,length,low);
/// read in the other cars' data
///cout << "\nEnter the other " << numberOfCars-1 << " cars: ";
vector > spaces(numberOfLanes, vector(1));
///test vector of vectors
/**for(int i = 0; i < numberOfLanes; ++i)
for(int j = 0; j < spaces[i].size(); ++j)
cout << spaces[i][j] << endl;*/
for(int i = 0; i < numberOfCars-1; ++i) {
read >> lane >> length >> low;
spaces[lane].push_back(low);
spaces[lane].push_back(low+length);
}
/// put sensor length at the end of each vector
for(int i = 0; i < numberOfLanes; ++i) {
spaces[i].push_back(lengthOfSensor);
}
print_spaces(spaces);
/**for(int i = 0; i < numberOfCars-1; ++i) {
cin >> lane >> length >> lowest;
highest = lowest + length;
vc.push_back(Car(lowest, highest, lane, length));
///cout << "\ni = " << i;
}*/
///cout << "\nThe ACM Car is ";
///acmCar.print();
///for(int i = 0; i < numberOfCars-1; ++i)
/// vc[i].print();
/// Compute Spaces
/// sort car vector by lanes
///vector > vcc;
///vcc = sortCarsByLanes(vc,numberOfCars,numberOfLanes);
///cout << endl;
///vcc[1][0].print();
}