Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <cassert>
- #include <cmath>
- #include <algorithm>
- #include <string>
- #include <vector>
- #include <queue>
- #include <list>
- #include <set>
- #include <map>
- using namespace std;
- #define eprintf(...) fprintf(stderr, __ VA_ARGS__)
- #define pb push_back
- #define mp make_pair
- #define sz(x) ((int)(x).size())
- #define TASKNAME "segments"
- typedef long long ll;
- typedef vector<ll> vll;
- typedef vector<int> vi;
- typedef vector<vi> vvi;
- typedef vector<bool> vb;
- typedef vector<vb> vvb;
- typedef pair<int, int> pii;
- #define EPS 1e-8
- struct pt {
- double x, y;
- pt(double _x = 0, double _y = 0) : x(_x), y(_y) {}
- bool operator<(const pt &p2) const {
- if (fabs(x - p2.x) < EPS) return x < p2.x;
- return y < p2.y - EPS;
- }
- bool operator==(const pt &p2) const { return fabs(x - p2.x) < EPS && fabs(y - p2.y) < EPS; }
- };
- struct line {
- double a, b, c;
- line(const pt &p1, const pt &p2) {
- a = p1.y - p2.y;
- b = p2.x - p1.x;
- c = -a * p1.x - b * p1.y;
- }
- bool cont(const pt &p) const { return fabs(a * p.x + b * p.y + c) < EPS; }
- pt operator&(const line &l2) {
- double d = a * l2.b - b * l2.a;
- if (fabs(d) < EPS) {
- if (fabs(a * l2.c - c * l2.a) < EPS && fabs(b * l2.c - c * l2.b) < EPS)
- throw 1;
- else
- throw 0;
- }
- pt res(
- (b * l2.c - c * l2.b) / d,
- (a * l2.c - c * l2.a) / -d
- );
- assert(cont(res) && l2.cont(res));
- return res;
- }
- };
- bool is_in(double x1, double x2, double x) {
- if (x1 > x2) swap(x1, x2);
- return x1 - EPS <= x && x <= x2 + EPS;
- }
- bool is_in(const pt &a, const pt &b, const pt &p) {
- return is_in(a.x, b.x, p.x) && is_in(a.y, b.y, p.y);
- }
- int main() {
- freopen(TASKNAME ".in", "r", stdin);
- freopen(TASKNAME ".out", "w", stdout);
- pt a1, a2, b1, b2;
- while (scanf("%lf%lf", &a1.x, &a1.y) >= 1) {
- scanf("%lf%lf", &a2.x, &a2.y);
- scanf("%lf%lf", &b1.x, &b1.y);
- scanf("%lf%lf", &b2.x, &b2.y);
- line l1(a1, a2), l2(b1, b2);
- vector<pt> res;
- try {
- res.pb(l1 & l2);
- } catch (int cnt) {
- eprintf("cnt=%d\n", cnt);
- if (cnt > 0) {
- res.pb(a1);
- res.pb(a2);
- res.pb(b1);
- res.pb(b2);
- }
- }
- sort(res.begin(), res.end());
- res.resize(unique(res.begin(), res.end()) - res.begin());
- vector<pt> res2;
- for (int i = 0; i < sz(res); i++) if (is_in(a1, a2, res[i]) && is_in(b1, b2, res[i]))
- res2.pb(res[i]);
- assert(sz(res2) <= 2);
- if (!sz(res2)) printf("Empty\n");
- else
- for (int i = 0; i < sz(res2); i++)
- printf("%.18e %.18e\n", res2[i].x, res2[i].y);
- break;
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment