Cod sursa(job #2843886)

Utilizator iraresmihaiiordache rares mihai iraresmihai Data 3 februarie 2022 10:26:33
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.43 kb
#include <iostream>
#include <fstream>
#include <math.h>
#include <algorithm>

using namespace std;

ifstream fin("triang.in");
ofstream fout("triang.out");

#define MAXN 1500
#define STEEP 10001
#define EPSILON 0.0000001

struct point{
  double x, y;
};

double f(double x) {
  if ( x >= 0 )
    return x;
  return -x;
}

bool comp(point a, point b) {
  if ( f(a.x - b.x) > EPSILON ) {
    return a.x < b.x;
  } else {
    return a.y < b.y;
  }
}

point m[MAXN];
int n;

void findRule(double x1, double y1, double x2, double y2, double& a, double& b) {
  if ( f(x2 - x1) > EPSILON ) {
    a = (y2 - y1) / (x2 - x1);
    b = y1 - x1 * a;
  }
  else {
    a = STEEP;
    b = x1;
  }
}

void calcMid(double x1, double y1, double x2, double y2, double& x, double& y) {
  x = (x1 + x2) / 2;
  y = (y1 + y2) / 2;
}

bool existPoint(double x, double y) {
  int st, dr, mid;

  st = 0;
  dr = n;
  while ( dr - st > 1 ) {
    mid = (st + dr) / 2;
    if ( m[mid].x > x && f(m[mid].x - x) > EPSILON )
      dr = mid;
    else
      st = mid;
  }

  if ( f(m[st].x - x) <= EPSILON ) {
    if ( m[st].y >= y ) {
      while ( st >= 0 && f(m[st].x - x) <= EPSILON && f(m[st].y - y) > EPSILON ) st--;
    } else {
      while ( st < n && f(m[st].x - x) <= EPSILON && f(m[st].y - y) > EPSILON ) st++;
    }

    if ( st >= 0 && st < n && f(m[st].x - x) <= EPSILON && f(m[st].y - y) <= EPSILON )
      return true;
  }
  return false;
}

int calcTri(double x1, double y1, double x2, double y2) {
  double xans1, xans2, yans1, yans2;
  int ans;

  ans = 0;
  xans1 = (x2 + x1) / 2 + sqrt(3) * (y2 - y1) / 2;
  xans2 = (x2 + x1) / 2 - sqrt(3) * (y2 - y1) / 2;
  yans1 = (y2 + y1) / 2 - sqrt(3) * (x2 - x1) / 2;
  yans2 = (y2 + y1) / 2 + sqrt(3) * (x2 - x1) / 2;

  if ( (xans1 > x2 && (f(xans1 - x2) > EPSILON)) || (f(xans1 - x2) <= EPSILON && yans1 > y2) )
    ans += existPoint(xans1, yans1);

  if ( (xans2 > x2 && f(xans2 - x2) > EPSILON) || (f(xans2 - x2) <= EPSILON && yans2 > y2) )
    ans += existPoint(xans2, yans2);

  return ans;
}

int main() {
  int i, ans, i2;

  fin >> n;

  for ( i = 0; i < n; i++ ) {
    fin >> m[i].x >> m[i].y;
  }

  sort(m, m + n, comp);

  ans = 0;
  for ( i = 0; i < n; i++ ) {
    for ( i2 = i + 1; i2 < n; i2++ ) {
      ans += calcTri(m[i].x, m[i].y, m[i2].x, m[i2].y);
    }
  }

  fout << ans;

  fin.close();
  fout.close();

  return 0;
}