Cod sursa(job #2843859)

Utilizator vladburacBurac Vlad vladburac Data 3 februarie 2022 01:56:43
Problema Triang Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.39 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <math.h>
#include <map>
using namespace std;
#define NMAX 1500
#define VALMAX 20000
#define EPS 0.000001

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

struct point{
  double x, y;
};
point v[NMAX];
double dist[NMAX][NMAX];

double distance( double x1, double y1, double x2, double y2 ) {
  return sqrt( ( y2 - y1 ) * ( y2 - y1 ) + ( x2 - x1 ) * ( x2 - x1 ) );
}

int main() {
  int n, i, j, nr, st, dr, mij;
  double d;
  fin >> n;
  for( i = 0; i < n; i++ )
    fin >> v[i].x >> v[i].y;
  for( i = 0; i < n; i++ ) {
    for( j = 0; j < n; j++ ) {
      if( i != j )
        dist[i][j] = distance( v[i].x, v[i].y, v[j].x, v[j].y );
    }
  }
  for( i = 0; i < n; i++ )
    sort( dist[i], dist[i] + n );
  nr = 0;
  for( i = 0; i < n; i++ ) {
    for( j = i + 1; j < n; j++ ) {
      if( i != j ) {
        d = distance( v[i].x, v[i].y, v[j].x, v[j].y );
        st = 0;
        dr = n;
        while( dr - st > 1 ) {
          mij = ( st + dr ) / 2;
          if( dist[i][mij] - EPS > d )
            dr = mij;
          else
            st = mij;
        }
        while( st > 0 && dist[i][st] + EPS >= d && dist[i][st] - EPS <= d ) {
          if( st != j && distance( v[st].x, v[st].y, v[j].x, v[j].y ) + EPS >= d && distance( v[st].x, v[st].y, v[j].x, v[j].y ) - EPS <= d )
            nr++;
          st--;
        }
      }
    }
  }
  fout << nr / 3;
  /*
  nr = 0;
  for( i = 0; i < n; i++ ) {
    for( j = 0; j < n; j++ ) {
      if( i != j ) {
        if( v[j].x == v[i].x ) {
          coordx = v[i].x + sqrt(3) / 2 * ( v[j].y - v[i].y );
          if( coord[coordx] + EPS >= ( v[j].y + v[i].y ) / 2 && coord[coordx] - EPS <= ( v[j].y + v[i].y ) / 2 )
            nr++;
          coordx = v[i].x - sqrt(3) / 2 * ( v[j].y - v[i].y );
          if( coord[coordx] + EPS >= ( v[j].y + v[i].y ) / 2 && coord[coordx] - EPS <= ( v[j].y + v[i].y ) / 2 )
            nr++;
        }
        else if( v[j].y == v[i].y ) {
          coordy = v[i].y + sqrt(3) / 2 * ( v[j].x - v[i].x );
          if( coord[( v[i].x + v[j].x ) / 2] + EPS >= coordy && coord[( v[i].x + v[j].x ) / 2] - EPS <= coordy )
            nr++;
          coordy = v[i].y - sqrt(3) / 2 * ( v[j].x - v[i].x );
          if( coord[( v[i].x + v[j].x ) / 2] + EPS >= coordy && coord[( v[i].x + v[j].x ) / 2] - EPS <= coordy )
            nr++;
        }
        else {
          a1 = ( v[j].y - v[i].y ) / ( v[j].x - v[i].x );
          // y1 = a1 * x1 + b1
          b1 = v[j].y - a1 * v[j].x;
          mid = { ( v[i].x + v[j].x ) / 2, ( v[i].y + v[j].y ) / 2 };
          a2 = -a1;
          // ymid = a2 * xmid + b2
          b2 = mid.y - a2 * mid.x;
          dist = distance( v[i].x, v[i].y, v[j].x, v[j].y );
          a = a2 * a2 + 1;
          b = 2 * a2 * b2 - 2 * a2 * mid.y - 2 * mid.x;
          c = mid.x * mid.x + b2 * b2 + mid.y * mid.y - 2 * mid.y * b2 - dist * dist * 3 / 4;
          delta = b * b - 4 * a * c;
          sol1 = ( -b + sqrt(delta) ) / ( 2 * a );
          sol2 = ( -b - sqrt(delta) ) / ( 2 * a );
          if( coord[sol1] + EPS >= a2 * sol1 + b2 && coord[sol1] - EPS <= a2 * sol1 + b2 )
            nr++;
          if( coord[sol2] + EPS >= a2 * sol2 + b2 && coord[sol2] - EPS <= a2 * sol2 + b2 )
            nr++;
        }
      }
    }
  }
  fout << nr; */
  return 0;
}