Return to Answer

Also your lack of using std:: before vector indicates you are using using namespace std; in some place in your code. Please stop doing that. See Why is "using namespace std;" considered bad practice?

Also your lack of using std:: before vector indicates you are using using namespace std; in some place in your code. Please stop doing that. See Why is "using namespace std;" considered bad practice?

###Bridge class Bridge { int id; Point start; Point end; public: friend std::istream& operator>>(std::istream& in, Bridge& data) { std::string line; if(std::getline(in, line)) { std::stringstream lineStream(line); char c[10]; lineStream >> data.id >> c[0] >> c[1] >> c[2] >> data.start.x >> c[3] >> data.start.y >> c[4] >> c[5] >> c[6] >> data.end.x >> c[7] >> data.end.y >> c[8] >> c[9]; if (c[0] != ':' || c[1] != '(' || c[2] != '[' || c[3] != ',' || c[4] != ']' || c[5] != ',' || c[6] != '[' || c[7] != ',' || c[8] != ']' || c[9] != ')') { throw std::runtime_error("Failed: Input error"); } } return in; } friend std::ostream& operator<<(std::ostream& out, Bridge& data) { return out << data.id; }

 bool Intersect(Bridge const& rhs) const
 {
 bool r = (id == rhs.id)
 ? true
 : doIntersect(start, end, rhs.start, rhs.end);
 return r;
 }
};

###BridgeCross class BridgeCross { std::vector const& data; // All the bridges std::vector<std::vector> validBridges; public: BridgeCross(std::vector const& data) : data(data) , validBridges(data.size(), std::vector(data.size(), -1)) {}

 bool isBridegeOK(int src, int dst)
 {
 int x = std::min(src, dst);
 int y = std::max(src, dst);
 
 int& test = validBridges[x][y];
 if (test == -1)
 {
 test = data[x].Intersect(data[y]);
 }
 return !test;
 }
};

###main int main() { std::vector bridges; std::copy(std::istream_iterator(std::cin), std::istream_iterator(), std::back_inserter(bridges));

 BridgeCross bridgeCrossInfo(bridges);
 typedef std::set<int> DataSet;
 typedef std::set<DataSet> ContSet;
 ContSet bridgeSets;
 DataSet bestSetSoFar;
 std::size_t const size = bridges.size();
 bridgeSets.insert(DataSet()); // Adds an empty set.
 for(int loop = 0; loop < size; ++loop)
 {
 ContSet replacement;
 bool haveBestSetAtThisSize = false;
 for(auto const& check: bridgeSets)
 {
 bool noChangeAdd = true;
 for(int test = 0; test < size; ++test)
 {
 if (std::find_if(check.begin(), check.end(),
 [&bridgeCrossInfo, &test](int val)
 {
 bool t = !bridgeCrossInfo.isBridegeOK(test, val);
 return t;
 }
 ) == check.end())
 {
 DataSet result(check);
 result.insert(test);
 replacement.insert(std::move(result));
 noChangeAdd = false;
 }
 else
 {
 }
 }
 if (noChangeAdd && !haveBestSetAtThisSize)
 {
 // In every iteration there may be multiple best results
 // It does not matter which one we choose.
 // So choose the first and avoid the extra copies.
 haveBestSetAtThisSize = true;
 bestSetSoFar = check;
 }
 }
 replacement.swap(bridgeSets);
 }
 if (!bridgeSets.empty())
 {
 // If this is not empty. Then we managed to add all the bridges and thus have a full set of bridges.
 bestSetSoFar= *(bridgeSets.begin());
 }
 for(auto loop = bestSetSoFar.begin(); loop != bestSetSoFar.end(); ++loop)
 {
 std::cout << bridges[*loop] << "\n";
 }
}

This section contains the line intersection detection code. Which I found here I just changed the Point structure to hold doubles rather than integers. This meant I needed to update the orientation() function (as test for zero was needed) and I made it test up to 6 decimal places of accuracy (which matched the sample input data).

###Bridge

A class for reading and writing bridge information from/to a stream. Just one extra function to detect intersection between two bridges.

class Bridge
{
 int id;
 Point start;
 Point end;
 public:
 friend std::istream& operator>>(std::istream& in, Bridge& data)
 {
 std::string line;
 if(std::getline(in, line))
 {
 std::stringstream lineStream(line);
 char c[10];
 lineStream >> data.id >> c[0] >> c[1] >> c[2] >> data.start.x >> c[3] >> data.start.y >> c[4] >> c[5] >> c[6] >> data.end.x >> c[7] >> data.end.y >> c[8] >> c[9];
 if (c[0] != ':' || c[1] != '(' || c[2] != '[' || c[3] != ',' || c[4] != ']' || c[5] != ',' || c[6] != '[' || c[7] != ',' || c[8] != ']' || c[9] != ')')
 {
 throw std::runtime_error("Failed: Input error");
 }
 }
 return in;
 }
 friend std::ostream& operator<<(std::ostream& out, Bridge& data)
 {
 return out << data.id;
 }
 bool Intersect(Bridge const& rhs) const
 {
 bool r = (id == rhs.id)
 ? true
 : doIntersect(start, end, rhs.start, rhs.end);
 return r;
 }
};

###BridgeCross

A class to cache information about weather two bridges cross. The first time you ask it calculates the value. Subsequent requests just use the previous value.

class BridgeCross
{
 std::vector<Bridge> const& data; // All the bridges
 std::vector<std::vector<int>> validBridges;
 public:
 BridgeCross(std::vector<Bridge> const& data)
 : data(data)
 , validBridges(data.size(), std::vector<int>(data.size(), -1))
 {}
 bool isBridegeOK(int src, int dst)
 {
 int x = std::min(src, dst);
 int y = std::max(src, dst);
 
 int& test = validBridges[x][y];
 if (test == -1)
 {
 test = data[x].Intersect(data[y]);
 }
 return !test;
 }
};

###main

I creat3ed a better version using boost::dynamic_bitset. But the compatition site did not have boost installed (I complained obviously).

int main()
{
 std::vector<Bridge>  bridges;
  std::copy(std::istream_iterator<Bridge>(std::cin), std::istream_iterator<Bridge>(),
 std::back_inserter(bridges));
 BridgeCross bridgeCrossInfo(bridges);
 typedef std::set<int> DataSet;
 typedef std::set<DataSet> ContSet;
 /*
 * DataSet: A set of bridges that work together.
 *  We are trying to build a bunch of these the set with the largest
  * number of members is the answer to the solution.
 * ContSet: A set of potential answers.
 * Each iteration of the outer loop we take each answer we already
 * have constructed and add each of the bridges to it.
 *
 *  We start with a single DataSet that has zero bridges.
 * After the first iteration we have N DataSets each with a different
 * bridge in it.
 * After the second iteration we have N*N DataSets with all
 * of combinations X,Y (assuming X and Y work together).
 *
 * So basically every iteration we do a cartesian product of the
 * the current result set and all the bridges in the input data.
 *
 * You would thinkg this woudl explode the data size required.
 * But you also have to remember that a lot of the combinations
 * produce the same set:
 * 1 + 2 + 3 => 2 + 1 + 3 => 2 + 3 + 1 => 3 + 1 + 2 => 3 + 2 + 1
 *
 * We also add the optimization that if we fail to add a bridge
 * we remove the set from the potential results (because we are
 * reying all results at the same time this optimization is fine
 * and does not limit us in finding the solution.
 */
 ContSet bridgeSets;
 DataSet bestSetSoFar;
 std::size_t const size = bridges.size();
 bridgeSets.insert(DataSet()); // Adds an empty set.
 /*
 * Two main loops. (loop and test) make sure we add all combinations.
 * The check loop iterates over all the current results.
 * The `std::find_if()` loops over all current bridges in a DataSet
 *
 * So this is technically a O(n^4) complexity.
 *
 * But in reality it automatically prunes itself well.
 * I don't have the maths skill to work out the true complexity.
 *
 */
 for(int loop = 0; loop < size; ++loop)
 {
 ContSet replacement;
 bool haveBestSetAtThisSize = false;
 for(auto const& check: bridgeSets)
 {
 bool noChangeAdd = true;
 for(int test = 0; test < size; ++test)
 {
 if (std::find_if(check.begin(), check.end(),
 [&bridgeCrossInfo, &test](int val)
 {
 bool t = !bridgeCrossInfo.isBridegeOK(test, val);
 return t;
 }
 ) == check.end())
 {
 DataSet result(check);
 result.insert(test);
 replacement.insert(std::move(result));
 noChangeAdd = false;
 }
 else
 {
 }
 }
 if (noChangeAdd && !haveBestSetAtThisSize)
 {
 // In every iteration there may be multiple best results
 // It does not matter which one we choose.
 // So choose the first and avoid the extra copies.
 haveBestSetAtThisSize = true;
 bestSetSoFar = check;
 }
 }
 replacement.swap(bridgeSets);
 }
 if (!bridgeSets.empty())
 {
 // If this is not empty. Then we managed to add all the bridges and thus have a full set of bridges.
 bestSetSoFar= *(bridgeSets.begin());
 }
 // Just print out the bridges in the bestSetSoFar.
 // DataSet is a sorted set so it should come out in the correct order
 // with no work.
 for(auto loop = bestSetSoFar.begin(); loop != bestSetSoFar.end(); ++loop)
 {
 std::cout << bridges[*loop] << "\n";
 }
}

Don't need to typedef struct in C++ like you did in C. struct are already in the normal namespace (not their own). Also its nice to indent the code to make it nice to read.

Don't declare all your variables a the top of the function.

You put lots of minuta code into the main function. You should put this code into its own function. I persnally define the std::istream operator>>(std::ostream&, Bridges&) method. This way a bridge knows how to read itself from the input. Your basic code is then simplifies too:

Its O(N^2). I tried looking at DoLineSegmentsIntersect() to see if I could spot a smarter way of applying this. But because the variable names make it incomprehensible to decipher (and there is no comments) I can't help you there. But maybe you don't have to search all the bridges. If you use a map to keep an ordered set of bridges maybe you can just extract lists of map that have a specific property.

Don't need to typedef struct in C++ like you did in C. struct are already in the normal namespace (not their own). Also its nice to indent the code to make it nice to read.

Don't declare all your variables at the top of the function.

You put lots of minuta code into the main function. You should put this code into its own function. I personally define the std::istream operator>>(std::ostream&, Bridges&) method. This way a bridge knows how to read itself from the input. Your basic code is then simplifies too:

It's \$O(N^2)\$. I tried looking at DoLineSegmentsIntersect() to see if I could spot a smarter way of applying this. But because the variable names make it incomprehensible to decipher (and there is no comments) I can't help you there. But maybe you don't have to search all the bridges. If you use a map to keep an ordered set of bridges maybe you can just extract lists of map that have a specific property.