Cod sursa(job #1021933)

Utilizator bghimisFMI Ghimis Bogdan bghimis Data 4 noiembrie 2013 14:57:07
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;

ifstream cin("triang.in");
ofstream cout("triang.out");

const double rad3 = 1.73205081;

struct Point
{
  double x;
  double y;

  inline bool operator==(Point other)
  {
    return (x == other.x &&
	    y == other.y);
  }
};
Point p[1501];
vector<Point> myHash[700001]; 

int hashFunc (int nr)
{
  return nr % 700001;
}
 
void adaugare (Point val)
{ 
  myHash[hashFunc((int)val.x)].push_back(val);
}
 
int cauta(Point val)
{
  int hashed = hashFunc((int)val.x);
  for (vector<Point>::iterator i = myHash[hashed].begin(); i != myHash[hashed].end(); ++i)
    if (*i == val)
      return 1;
  
  return 0;
}

void stergere (Point val)
{
  int hashed = hashFunc(val.x);
  
  for (vector<Point>::iterator i = myHash[hashed].begin(); i != myHash[hashed].end(); ++i)
    if (*i == val)
      {
	myHash[hashed].erase(i);
	return;
      }
}

int main()
{
  int n; cin >> n;
  for (int i = 1; i <= n; ++i)
    cin >> p[i].x >> p[i].y;

  for (int i = 1; i <= n; ++i)
    for (int j = i + 1; j <= n; ++j)
      {
	double x1 = p[i].x + p[i].y * rad3 
	  + p[j].x - p[j].y * rad3;
	double y1 = -p[i].x * rad3 + p[i].y
	  + p[j].y + p[j].x * rad3;
	
	Point aux;
	aux.x = x1 / 2.0;
	aux.y = y1 / 2.0;

	aux.x = round(aux.x * 1000.0) / 1000.0;
	aux.y = round(aux.y * 1000.0) / 1000.0;

	adaugare (aux);

	x1 = p[i].x + p[j].x + 
	  (p[j].y - p[i].y) * rad3;
	y1 = p[i].x * rad3 + p[j].y 
	  + p[i].y - p[j].x * rad3;
	
	aux.x = x1 / 2.0;
	aux.y = y1 / 2.0;

	aux.x = round(aux.x * 1000.0) / 1000.0;
	aux.y = round(aux.y * 1000.0) / 1000.0;
	
	adaugare (aux);
      }

  int cnt = 0;
  for (int i = 1; i <= n; ++i)
    if (cauta (p[i]) == 1)
      {
	++cnt;
	stergere(p[i]);
      }

  cout << cnt / 2;

  return 0;
}