Cod sursa(job #2339617)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 9 februarie 2019 10:33:07
Problema Triang Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.86 kb
#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'

using namespace std;

typedef pair <int, int> pii;
typedef vector <int> vi;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int NMAX = 1505;
const ld EPS = 1e-6;

int sign (const ld x) {
  if (fabs (x) <= EPS) return 0;
  return (x < 0) ? -1 : 1;
}

struct Point {
  ld x, y;
  Point (ld _x = 0, ld _y = 0) : x (_x), y (_y) {}
  Point middle (const Point &other) {
    return {0.5 * (x + other.x), 0.5 * (y + other.y)};
  }
  ld sqrDist (const Point &other) {
    return ((x - other.x) * (x - other.x) + (y - other.y) * (y - other.y));
  }
  bool operator < (const Point &other) const {
    if (sign (x - other.x) == 0) return y < other.y;
    return x < other.x;
  }
  bool operator == (const Point &other) const {
    return sign (x - other.x) == 0 && sign (y - other.y) == 0;
  }
  bool operator != (const Point &other) const {
    return !(*this == other);
  }
};

struct Line {
  ld a, b, c;
  Line (ld _a = 0, ld _b = 0, ld _c = 0) : a (_a), b (_b), c (_c) {}
  Line (const Point &_a, const Point &_b) : a (_a.y - _b.y), b (_b.x - _a.x), c (_a.x * _b.y - _b.x * _a.y) {}
  Line perpendicular (const Point &p) {
    return {b, -a, a * p.y - b * p.x};
  }
  ld yAtX (const ld x) {
    return (-a / b) * x - c / b;
  }
  pair <Point, Point> pointAtDistance (const Point &p, const ld sqr_dist) {
    pair <Point, Point> ret;

    if (a == 0) {
      ret.fi.y = ret.se.y = p.y;
      ret.fi.x = p.x - sqrt (sqr_dist);
      ret.se.x = p.x + sqrt (sqr_dist);
      return ret;
    }
    if (b == 0) {
      ret.fi.x = ret.se.x = p.x;
      ret.fi.y = p.y - sqrt (sqr_dist);
      ret.se.y = p.y + sqrt (sqr_dist);
      return ret;
    }

    ld delta = b * sqrt ((a * a + b * b) * sqr_dist * sqr_dist * sqr_dist * sqr_dist - c * c);
    ld x = (-a * c + delta) / (a * a + b * b);
    ret.fi.x = p.x + x;
    ret.fi.y = yAtX (ret.fi.x);
    x = (-a * c - delta) / (a * a + b * b);
    ret.se.x = p.x + x;
    ret.se.y = yAtX (ret.se.x);

    assert (ret.fi != ret.se);

    return ret;
  }
};

int n;
Point points[NMAX];

bool check (const Point &p, const Point &comp) {
  if (sign (p.x - comp.x) != 0) return p.x < comp.x;
  return sign (p.y - comp.y) <= 0;
}

bool findPoint (int lo, const Point &p) {
  if (lo > n) return false;
  int hi = n;
  while (lo < hi) {
    int mid = lo + (hi - lo + 1) / 2;
    if (check (points[mid], p)) {
      lo = mid;
    } else {
      hi = mid - 1;
    }
  }

  return check (points[lo], p);
}

const ld sin60 = sqrt (3) / 2;
const ld cos60 = 0.5;
const ld sin_min60 = -sin60;
const ld cos_min60 = cos60;

pair <Point, Point> getThird (Point a, Point b) {
  ld x = b.x - a.x;
  ld y = b.y - a.y;

  pair <Point, Point> ret;
  ret.fi.x = a.x + x * cos60 - y * sin60;
  ret.fi.y = a.y + y * cos60 + x * sin60;
  ret.se.x = a.x + x * cos_min60 - y * sin_min60;
  ret.se.y = a.y + y * cos_min60 + x * sin_min60;

  return ret;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
#ifdef LOCAL_DEFINE
  freopen (".in", "r", stdin);
#endif

  ifstream f ("triang.in");
  ofstream g ("triang.out");

  f >> n;
  for (int i = 1; i <= n; ++i) {
    f >> points[i].x >> points[i].y;
  }
  sort (points + 1, points + n + 1);

  int answer = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = i + 1; j <= n; ++j) {
      pair <Point, Point> c = getThird (points[i], points[j]);
      if (findPoint (j + 1, c.fi)) ++answer;
      if (findPoint (j + 1, c.se)) ++answer;
    }
  }

  g << answer << '\n';

  f.close();
  g.close();

#ifdef LOCAL_DEFINE
  fprintf (stderr, "Time elapsed: %lf s.\n", 1.0 * clock() / CLOCKS_PER_SEC);
#endif
  return 0;
}