Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define REP(i, n) for(int i = 0; i < n; i++)
- #define FOR(i, a, b) for(int i = a; i <= b; i++)
- #define ST first
- #define ND second
- ostream& operator<<(ostream &out, string str) {
- for(char c : str) out << c;
- return out;
- }
- template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) {
- return out << "(" << p.ST << ", " << p.ND << ")";
- }
- template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
- out << "{";
- for(auto it = a.begin(); it != a.end(); it = next(it))
- out << (it != a.begin() ? ", " : "") << *it;
- return out << "}";
- }
- void dump() { cerr << "\n"; }
- template<class T, class... Ts> void dump(T a, Ts... x) {
- cerr << a << ", ";
- dump(x...);
- }
- #ifdef DEBUG
- # define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
- #else
- # define debug(...) false
- #endif
- template<class T> int size(T && a) { return a.size(); }
- using LL = long long;
- using PII = pair<int, int>;
- int sign(LL x) {
- if(x < 0) return -1;
- if(x > 0) return +1;
- return 0;
- }
- LL cross(PII a, PII b) {
- return (LL) a.ST * b.ND - a.ND * b.ST;
- }
- PII operator-(PII a, PII b) {
- return {a.ST - b.ST, a.ND - b.ND};
- }
- int side(PII a, PII b, PII p) {
- return sign(cross(b - a, p - a));
- }
- vector<int> rep;
- int find(int x) {
- return rep[x] == x ? x : rep[x] = find(rep[x]);
- }
- bool join(int x, int y) {
- x = find(x), y = find(y);
- if(x == y) return false;
- rep[x] = y;
- return true;
- }
- double dst(PII a, PII b) {
- LL x = a.ST - b.ST, y = a.ND - b.ND;
- return sqrt(x * x + y * y);
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- int n;
- cin >> n;
- vector<PII> p(n), q(n);
- REP(i, n) cin >> p[i].ST >> p[i].ND >> q[i].ST >> q[i].ND;
- rep.resize(n);
- REP(i, n) rep[i] = i;
- int edges = 0, comps = n;
- REP(i, n) {
- REP(j, i) {
- bool a = side(p[i], q[i], p[j]) != side(p[i], q[i], q[j]);
- bool b = side(p[j], q[j], p[i]) != side(p[j], q[j], q[i]);
- bool good = a && b;
- if(side(p[i], q[i], p[j]) == 0 && !a) {
- double max_dst = 0;
- for(auto &x : {p[i], q[i]})
- for(auto &y : {p[j], q[j]})
- max_dst = max(max_dst, dst(x, y));
- if(max_dst <= dst(p[i], q[i]) + dst(p[j], q[j]) + 1e-9)
- good = true;
- }
- if(good) {
- edges++;
- comps -= join(i, j);
- }
- }
- }
- cout << edges - n + comps + 1 << "\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement