#include <iostream> #include <vector> #include <algorithm> #include <cmath> // generate pseudo-random numbers (Blum Blum Shub algorithm) unsigned int next() { static unsigned long long seed = 290797; seed *= seed; seed %= 50515093; return seed % 500; } // a 2D point struct Point { double x, y; // needed for std::unique bool operator==(const Point& other) const { return x == other.x && y == other.y; } // needed for std::sort bool operator< (const Point& other) const { if (x != other.x) return x < other.x; else return y < other.y; } }; // define a segment struct Segment { Point from, to; }; // find intersection of two segments, out parameter "where" is only valid if function returns true bool intersect(const Segment& segment1, const Segment& segment2, Point& where) { // shorter names for the four endpoints auto a = segment1.from; auto b = segment1.to; auto c = segment2.from; auto d = segment2.to; // store slope in a Point (just because I'm lazy and don't want to introduce another data type) Point slope1, slope2; slope1.x = b.x - a.x; slope1.y = b.y - a.y; slope2.x = d.x - c.x; slope2.y = d.y - c.y; auto determinant = slope1.x * slope2.y - slope2.x * slope1.y; // parallel ? if (determinant == 0) return false; // now the lines intersect, but not necessarily the segments auto s = (slope1.x * (a.y - c.y) - slope1.y * (a.x - c.x)) / determinant; auto t = (slope2.x * (a.y - c.y) - slope2.y * (a.x - c.x)) / determinant; // parameters s and t must be in (0 ... 1) // borders (=endpoints) are not true intersections according to problem statement if (s <= 0 || s >= 1 || t <= 0 || t >= 1) return false; // yes, intersection found (might be a duplicate, though !) where.x = a.x + t * slope1.x; where.y = a.y + t * slope1.y; // cut off a few digits to avoid rounding issues const auto Precision = 0.00000001; where.x = round(where.x / Precision) * Precision; where.y = round(where.y / Precision) * Precision; return true; } int main() { std::vector<Segment> segments; std::vector<Point> intersections; unsigned int limit = 5000; std::cin >> limit; for (unsigned int i = 0; i < limit; i++) { // create "random" segment Segment current; current.from.x = next(); current.from.y = next(); current.to .x = next(); current.to .y = next(); // try to intersect with all other segments Point where; for (auto compare : segments) if (intersect(current, compare, where)) intersections.push_back(where); // add current segment to list of segments segments.push_back(current); } // eliminate duplicate intersection points std::sort(intersections.begin(), intersections.end()); auto garbage = std::unique(intersections.begin(), intersections.end()); intersections.erase(garbage, intersections.end()); // display result std::cout << intersections.size() << std::endl; return 0; }
Write, Run & Share C++ code online using OneCompiler's C++ online compiler for free. It's one of the robust, feature-rich online compilers for C++ language, running on the latest version 17. Getting started with the OneCompiler's C++ compiler is simple and pretty fast. The editor shows sample boilerplate code when you choose language as C++
and start coding!
OneCompiler's C++ online compiler supports stdin and users can give inputs to programs using the STDIN textbox under the I/O tab. Following is a sample program which takes name as input and print your name with hello.
#include <iostream>
#include <string>
using namespace std;
int main()
{
string name;
cout << "Enter name:";
getline (cin, name);
cout << "Hello " << name;
return 0;
}
C++ is a widely used middle-level programming language.
When ever you want to perform a set of operations based on a condition If-Else is used.
if(conditional-expression) {
//code
}
else {
//code
}
You can also use if-else for nested Ifs and If-Else-If ladder when multiple conditions are to be performed on a single variable.
Switch is an alternative to If-Else-If ladder.
switch(conditional-expression){
case value1:
// code
break; // optional
case value2:
// code
break; // optional
......
default:
code to be executed when all the above cases are not matched;
}
For loop is used to iterate a set of statements based on a condition.
for(Initialization; Condition; Increment/decrement){
//code
}
While is also used to iterate a set of statements based on a condition. Usually while is preferred when number of iterations are not known in advance.
while (condition) {
// code
}
Do-while is also used to iterate a set of statements based on a condition. It is mostly used when you need to execute the statements atleast once.
do {
// code
} while (condition);
Function is a sub-routine which contains set of statements. Usually functions are written when multiple calls are required to same set of statements which increases re-usuability and modularity. Function gets run only when it is called.
return_type function_name(parameters);
function_name (parameters)
return_type function_name(parameters) {
// code
}