[Link] https://www.acmicpc.net/problem/20149
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cstring>
#include <stack>
#include <cmath>
// #include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define command_param int argc, char *argv[]
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i < n; i++)
#define fori(s, e) for(int i = s; i < e; i++)
#define ll long long
#define endl "\n"
#define nulls '\0'
#define dkdk " "
const int MAX = 2002;
const int INF = 987654321;
const int OPPOSITE = 1;
const int ONEZERO = 2;
const int TWOZERO = 3;
const int SAMESIDE = 4;
struct line {
pair<int, int> p1, p2;
};
int n, size1, size2;
line l1, l2;
int cross_check(line base, line line) {
int di1 = line.p1.first - base.p1.first, dj1 = line.p1.second - base.p1.second;
int di2 = line.p2.first - base.p1.first, dj2 = line.p2.second - base.p1.second;
int base_di = base.p2.first - base.p1.first, base_dj = base.p2.second - base.p1.second;
ll outer_product1 = (ll)di1*base_dj - (ll)base_di*dj1, outer_product2 = (ll)di2*base_dj - (ll)base_di*dj2;
if((outer_product1 > 0 && outer_product2 > 0) || (outer_product1 < 0 && outer_product2 < 0)) return SAMESIDE;
if(outer_product1 == 0 && outer_product2 == 0) return TWOZERO;
if(outer_product1 == 0 || outer_product2 == 0) return ONEZERO;
return OPPOSITE;
}
pair<double, double> intersection(line base, line line) {
int di1 = line.p1.first - base.p1.first, dj1 = line.p1.second - base.p1.second;
int di2 = line.p2.first - base.p1.first, dj2 = line.p2.second - base.p1.second;
int base_di = base.p2.first - base.p1.first, base_dj = base.p2.second - base.p1.second;
ll outer_product1 = (ll)di1*base_dj - (ll)base_di*dj1, outer_product2 = (ll)di2*base_dj - (ll)base_di*dj2;
double ratio = (double)abs(outer_product1) / (abs(outer_product1) + abs(outer_product2));
pair<double, double> ans;
ans.first = line.p1.first + (line.p2.first - line.p1.first) * ratio;
ans.second = line.p1.second + (line.p2.second - line.p1.second) * ratio;
return ans;
}
int main() {
FASTIO;
cout << fixed; cout.precision(12);
cin >> l1.p1.first >> l1.p1.second >> l1.p2.first >> l1.p2.second;
cin >> l2.p1.first >> l2.p1.second >> l2.p2.first >> l2.p2.second;
int check1 = cross_check(l1, l2), check2 = cross_check(l2, l1);
// cout << "check ? " << check1 << " and " << check2 << endl;
if(check1 == SAMESIDE || check2 == SAMESIDE) {
cout << 0;
return 0;
}
if(check1 == TWOZERO && check2 == TWOZERO) {
if(max(l1.p1.first, l1.p2.first) < min(l2.p1.first, l2.p2.first) || max(l2.p1.first, l2.p2.first) < min(l1.p1.first, l1.p2.first) ||
max(l1.p1.second, l1.p2.second) < min(l2.p1.second, l2.p2.second) || max(l2.p1.second, l2.p2.second) < min(l1.p1.second, l1.p2.second))
cout << 0;
else {
cout << 1 << endl;
if(l1.p1.first == l1.p2.first && l2.p1.first == l2.p2.first) {
if(min(l1.p1.second, l1.p2.second) <= min(l2.p1.second, l2.p2.second) && min(l2.p1.second, l2.p2.second) < max(l1.p1.second, l1.p2.second))
return 0;
if(min(l2.p1.second, l2.p2.second) <= min(l1.p1.second, l1.p2.second) && min(l1.p1.second, l1.p2.second) < max(l2.p1.second, l2.p2.second))
return 0;
}
else {
if(min(l1.p1.first, l1.p2.first) <= min(l2.p1.first, l2.p2.first) && min(l2.p1.first, l2.p2.first) < max(l1.p1.first, l1.p2.first))
return 0;
if(min(l2.p1.first, l2.p2.first) <= min(l1.p1.first, l1.p2.first) && min(l1.p1.first, l1.p2.first) < max(l2.p1.first, l2.p2.first))
return 0;
}
pair<int, int> tmp;
if(l1.p1.first == l2.p1.first && l1.p1.second == l2.p1.second) tmp = l1.p1;
if(l1.p1.first == l2.p2.first && l1.p1.second == l2.p2.second) tmp = l1.p1;
if(l1.p2.first == l2.p1.first && l1.p2.second == l2.p1.second) tmp = l1.p2;
if(l1.p2.first == l2.p2.first && l1.p2.second == l2.p2.second) tmp = l1.p2;
cout << tmp.first << " " << tmp.second;
}
return 0;
}
if(check1 == ONEZERO && check2 == ONEZERO) {
cout << 1 << endl;
pair<int, int> tmp;
if(l1.p1.first == l2.p1.first && l1.p1.second == l2.p1.second) tmp = l1.p1;
if(l1.p1.first == l2.p2.first && l1.p1.second == l2.p2.second) tmp = l1.p1;
if(l1.p2.first == l2.p1.first && l1.p2.second == l2.p1.second) tmp = l1.p2;
if(l1.p2.first == l2.p2.first && l1.p2.second == l2.p2.second) tmp = l1.p2;
cout << tmp.first << " " << tmp.second;
return 0;
}
pair<double, double> point;
if(check1 == ONEZERO) point = intersection(l2, l1);
else point = intersection(l1, l2);
cout << "1\n" << point.first << " " << point.second;
return 0;
}