Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define all(x) x.begin(), x.end()
- #define rall(x) x.rbegin(), x.rend()
- #define F first
- #define S second
- #define pb push_back
- #define ll long long
- #define ld long double
- #define double long double
- using namespace std;
- const double EPS = 1e-12;
- const double INF = 1e9;
- struct point;
- struct line;
- struct Vector;
- vector<point> p;
- //-----------POINT---------------
- struct point {
- double x, y;
- point(double a, double b) : x(a), y(b) {};
- point() {};
- };
- istream& operator>>(istream &is, point &dt)
- {
- is >> dt.x >> dt.y;
- return is;
- }
- ostream &operator<<(ostream &is, point &dt)
- {
- is << dt.x << " " << dt.y;
- return is;
- }
- bool operator==(point &a, point &b) {
- if (a.x == b.x && a.y == b.y) return 1;
- return 0;
- }
- //-----------VECTOR---------------
- struct Vector {
- double x, y;
- Vector operator+(Vector & other) {
- return {x + other.x, y + other.y};
- }
- Vector operator/(double a) {
- return {x / a, y / a};
- }
- Vector operator*(double a) {
- return {x * a, y * a};
- }
- double length() {
- return sqrt(x * x + y * y);
- }
- void normal() {
- double len = length();
- x = x / len;
- y = y / len;
- }
- Vector(const point p1, const point p2) : x(p2.x - p1.x), y(p2.y - p1.y) {};
- Vector(double x, double y) : x(x), y(y) {};
- };
- point operator+(Vector a, point b) {
- b.x += a.x;
- b.y += a.y;
- return b;
- }
- //-----------LINE---------------
- struct line {
- double a, b, c;
- line(point x1, point x2) : a(x2.y - x1.y), b(x1.x - x2.x), c(-a * x1.x - b * x1.y) {};
- };
- ostream& operator<<(ostream &is, line &dt)
- {
- is << dt.a << " " << dt.b << " " << dt.c;
- return is;
- }
- //-----------SOLVE---------------
- double scalar(Vector a, Vector b) {
- return (a.x * b.x + a.y * b.y);
- }
- double Pscalar(Vector a, Vector b) {
- return (a.x * b.y - a.y * b.x);
- }
- point lineIntersection(line line1, line line2) {
- double x, y;
- double a, b;
- a = (line1.c * line2.b - line2.c * line1.b);
- b = (line1.a * line2.b - line2.a * line1.b);
- x = -(a / b);
- a = (line1.a * line2.c - line2.a * line1.c);
- b = (line1.a * line2.b - line2.a * line1.b);
- y = -(a / b);
- return {x, y};
- }
- double distLine(point p, line a) {
- double ans = 0;
- ans = fabs(((a.a * p.x) + (a.b * p.y) + a.c) / (sqrt(a.a * a.a + a.b * a.b)));
- return ans;
- }
- bool OnLine(point p, line l) {
- if (l.a * p.x + l.b * p.y + l.c == 0) {
- return 1;
- }
- return 0;
- }
- bool pointOnSegment(point p, point s, point t) {
- line l(s, t);
- if (OnLine(p, l) && scalar(Vector(s, p), Vector(t, p)) <= 0) {
- return 1;
- }
- return 0;
- }
- bool checkSegments(point s1, point t1, point s2, point t2) {
- if (pointOnSegment(s1, s2, t2) || pointOnSegment(t1, s2, t2) || pointOnSegment(s2, s1, t1) || pointOnSegment(t2, s1, t1)) return 1;
- Vector A(s1, t1);
- Vector B(s2, t2);
- if ((Pscalar(A, Vector(t1, s2)) * Pscalar(A, Vector(t1, t2)) < 0) &&
- (Pscalar(B, Vector(t2, t1)) * Pscalar(B, Vector(t2, s1)) < 0)) {
- return 1;
- }
- return 0;
- }
- bool sidePolygon(int n, point s) {
- point t(s.x + INF + 5, s.y + 1);
- int cnt = 0;
- for (int i = 0; i < n - 1; i++) {
- if (checkSegments(s, t, p[i], p[i + 1])) cnt++;
- }
- if (checkSegments(s, t, p[n - 1], p[0])) cnt++;
- if (cnt % 2 == 0) {
- return 0;
- } else {
- return 1;
- }
- }
- void print_ans(point a, point b) {
- if (a == b) {
- cout << a.x << " " << a.y << "\n";
- exit(0);
- }
- if (a.x == b.x) {
- if (a.y < b.y) {
- cout << a.x << " " << a.y << "\n";
- cout << b.x << " " << b.y << "\n";
- exit(0);
- } else {
- cout << b.x << " " << b.y << "\n";
- cout << a.x << " " << a.y << "\n";
- exit(0);
- }
- }
- if (a.x > b.x) {
- cout << b.x << " " << b.y << "\n";
- cout << a.x << " " << a.y << "\n";
- exit(0);
- }
- cout << a.x << " " << a.y << "\n";
- cout << b.x << " " << b.y << "\n";
- exit(0);
- }
- bool cmp(point a, point b) {
- pair<double, double> c1 = {a.x, a.y};
- pair<double, double> c2 = {b.x, b.y};
- return c1 < c2;
- }
- int main() {
- freopen("segments.in", "r", stdin);
- freopen("segments.out", "w", stdout);
- cout << fixed;
- cout.precision(10);
- point a, b, c, d;
- cin >> a >> b >> c >> d;
- if ((a == c && b == d) || ((a == d) && (b == c))) {
- print_ans(a, b);
- return 0;
- }
- line c1(a, b);
- line c2(c, d);
- bool On1Line = Pscalar(Vector(a, b), Vector(c, d)) == 0 || Pscalar(Vector(a, b), Vector(d, c)) == 0;
- if (!On1Line && !checkSegments(a, b, c, d)) {
- cout << "Empty\n";
- return 0;
- }
- if (!On1Line && checkSegments(a, b, c, d)) {
- point ans = lineIntersection(c1, c2);
- cout << ans.x << " " << ans.y << '\n';
- return 0;
- } else { //c1 == c2
- vector<point> ans;
- if (pointOnSegment(a, c, d)) {
- ans.pb(a);
- }
- if (pointOnSegment(b, c, d)) {
- ans.pb(b);
- }
- if (pointOnSegment(c, a, b)) {
- ans.pb(c);
- }
- if (pointOnSegment(d, a, b)) {
- ans.pb(d);
- }
- if (ans.empty()) {
- cout << "Empty\n";
- return 0;
- }
- sort(all(ans), cmp);
- if (ans.size() == 1) {
- cout << ans[0].x << " " << ans[0].y << '\n';
- return 0;
- }
- print_ans(ans[0], ans[ans.size() - 1]);
- return 0;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement