Cod sursa(job #2843997)

Utilizator vladburacBurac Vlad vladburac Data 3 februarie 2022 15:41:33
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 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];
pair <double, int> 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 ), j };
    }
  }
  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].first - EPS > d )
            dr = mij;
          else
            st = mij;
        }
        while( st > 0 && dist[i][st].first + EPS >= d && dist[i][st].first - EPS <= d ) {
          if( dist[i][st].second != i && dist[i][st].second != j && distance( v[dist[i][st].second].x, v[dist[i][st].second].y, v[j].x, v[j].y ) + EPS >= d && distance( v[dist[i][st].second].x, v[dist[i][st].second].y, v[j].x, v[j].y ) - EPS <= d )
            nr++;
          st--;
        }
      }
    }
  }
  fout << nr / 3;
  return 0;
}