Cod sursa(job #1739725)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 10 august 2016 00:59:32
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

#define MaxN 1500
#define EPS 1e-5

struct Point {
   double x, y;

   void read() {
      scanf("%lf %lf", &x, &y);
   }
};

Point v[MaxN];
double dist[MaxN][MaxN];
pair <double, int> sortedDistance[MaxN];

double euclideanDistance(const Point &a, const Point &b) {
   return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int main() {
   freopen("triang.in", "r", stdin);
   freopen("triang.out", "w", stdout);

   int N;
   scanf("%d", &N);
   for (int i = 0; i < N; i++) {
      v[i].read();
   }

   for (int i = 0; i < N; i++) {
      for (int j = i + 1; j < N; j++) {
         dist[i][j] = dist[j][i] = euclideanDistance(v[i], v[j]);
      }
   }

   int answer = 0;
   for (int i = 0; i < N - 2; i++) {
      for (int j = i + 1; j < N; j++) {
         sortedDistance[j - i - 1] = make_pair(dist[i][j], j);
      }
      sort(sortedDistance, sortedDistance + N - i);
      for (int j = i + 1; j < N - 1; j++) {
         int k = j + 1;
         while (k < N && sortedDistance[k].first - sortedDistance[j].first < EPS) {
            answer += fabs(dist[sortedDistance[j].second][sortedDistance[k].second] - sortedDistance[j].first) < EPS;
            k++;
         }
      }
   }

   printf("%d\n", answer);

   return 0;
}