Cod sursa(job #1785989)

Utilizator mariusn01Marius Nicoli mariusn01 Data 22 octombrie 2016 10:56:32
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include<fstream>
#include<algorithm>
#include<cmath>
#define EPS 0.000001
#define DIM 1510
#define x first
#define y second
using namespace std;

pair<double, double> v[DIM];

double X1, Y11, X2, Y2;
double x1, y11, x2, y2, t, a, b, A, B, C, d;
int sol, n;

int egal(double a, double b) {
  double d = a-b;
  if (d <= EPS && d >= -EPS)
    return 1;
  return 0;
}

int cauta(double x, double y) {
  int st = 1, dr = n;
  while (st <= dr) {
    int mid = (st + dr)/2;
    if (egal(v[mid].x, x) && egal(v[mid].y, y)) {
      return 1;
    }
    if (v[mid].x < x || ( egal(v[mid].x, x) && v[mid].y < y ))
      st = mid+1;
    else
      dr = mid-1;
  }
  return 0;
}

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

  fin>>n;
  for(int i=1;i<=n;i++)
    fin>>v[i].x>>v[i].y;
  sort(v+1,v+n+1);

  for (int i=1;i<n;i++)
    for (int j=i+1;j<=n;j++) {
      x1 = v[i].x;
      y11 = v[i].y;
      x2 = v[j].x;
      y2 = v[j].y;
      t = x2*x2 + y2*y2 - x1*x1 - y11*y11;
      a = 2*(x2-x1);
      b = 2*(y2-y11);
      d = (x2-x1)*(x2-x1) + (y2-y11)*(y2-y11);
      A = a*a + b*b;
      B = -2*a*t - 2*x1*b*b - 2*y11*a*b;
      C = t*t - 2*y11*b*t + b*b*(x1*x1 + y11*y11 - d);

      X1 = (-B-sqrt( B*B-4*A*C ))/(2*A);
      X2 = (-B+sqrt( B*B-4*A*C ))/(2*A);
      if (b == 0)
        Y11 = (y2+y11)/2.0;
      else
        Y11 = (t-a*X1)/b;
      if (b == 0)
        Y2 = (y2+y11)/2.0;
      else
        Y2 = (t-a*X2)/b;

      sol += cauta(X1, Y11);
      sol += cauta(X2, Y2);

    }
  fout<<sol;
  return 0;
}