• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Jul 22nd, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2. #define fst first
3. #define snd second
4.
5. using namespace std;
6.
7. typedef long long ll;
8. typedef pair<int, int> ii;
9.
10. const double inf = 1e100, eps = 1e-9;
11. const double PI = acos(-1.0L);
12.
13. int cmp (double a, double b = 0) {
14.     if (abs(a-b) < eps) return 0;
15.     return (a < b) ? -1 : +1;
16. }
17.
18. struct PT {
19.     double x, y;
20.     PT(double x = 0, double y = 0) : x(x), y(y) {}
21.     PT operator + (const PT &p) const { return PT(x+p.x, y+p.y); }
22.     PT operator - (const PT &p) const { return PT(x-p.x, y-p.y); }
23.     PT operator * (double c) const { return PT(x*c, y*c); }
24.     PT operator / (double c) const { return PT(x/c, y/c); }
25.
26.     bool operator <(const PT &p) const {
27.         if(cmp(x, p.x) != 0) return x < p.x;
28.         return cmp(y, p.y) < 0;
29.     }
30.     bool operator ==(const PT &p) const {
31.         return (cmp(x, p.x) || cmp(y, p.y));
32.     }
33. };
34.
35.
36. double dot (PT p, PT q) { return p.x * q.x + p.y*q.y; }
37. double cross (PT p, PT q) { return p.x * q.y - p.y*q.x; }
38.
39. bool parallel (PT a, PT b, PT c, PT d) {
40.     return cmp(cross(b - a, c - d)) == 0;
41. }
42.
43. PT computeLineIntersection (PT a, PT b, PT c, PT d) {
44.     b = b - a; d = c - d; c = c - a;
45.     assert(cmp(cross(b, d)) != 0); // checar sse sao paralelos
46.     return a + b * cross(c, d) / cross(b, d);
47. }
48.
49. int n;
50.
51. int main(){
52.     ios::sync_with_stdio(0); cin.tie(0);
53.     while(cin >> n && n){
54.         vector<pair<PT, PT>> line;
55.
56.         for(int i = 0; i < n; ++i){
57.             int x1, y1, x2, y2;
58.             cin >> x1 >> y1 >> x2 >> y2;
59.             line.push_back({PT(x1, y1), PT(x2, y2)});
60.         }
61.         vector<vector<int>> adj(n * n, vector<int>());
62.         map<PT, int> mp;
63.         int c = 0;
64.         for(int i = 0; i < n; ++i){
65.             vector<PT> now;
66.             for(int j = 0; j < n; ++j){
67.                 if(i == j) continue;
68.                 if(!parallel(line[i].fst, line[i].snd, line[j].fst, line[j].snd)){
69.                     PT aux = computeLineIntersection(line[i].fst, line[i].snd, line[j].fst, line[j].snd);
70.                     now.push_back(aux);
71.                 }
72.             }
73.             sort(now.begin(), now.end());
74.             for(int j = 1; j < ((int)now.size()); ++j){
75.                 if(!mp.count(now[j-1])){
76.                     mp[now[j-1]] = c++;
77.                 }
78.                 if(!mp.count(now[j])){
79.                     mp[now[j]] = c++;
80.                 }
83.             }
84.         }
85.         bool achou[c];
86.         int ans = 0;
87.         for(int i = 0; i < c; ++i){
88.             memset(achou, 0, sizeof achou);
89.             for(int j = 0; j < adj[i].size(); ++j){