Advertisement
Guest User

Untitled

a guest
Jul 22nd, 2019
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.93 KB | None | 0 0
  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.                 }
  81.                 adj[mp[now[j]]].push_back(mp[now[j-1]]);
  82.                 adj[mp[now[j-1]]].push_back(mp[now[j]]);
  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){
  90.                 achou[adj[i][j]] = 1;
  91.                 for(auto k : adj[adj[i][j]]){
  92.                     if(achou[k]) ans++;
  93.                 }
  94.             }
  95.         }
  96.         cout << ans/3 << '\n';
  97.     }
  98.     return 0;
  99. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement