Cod sursa(job #2766715)

Utilizator popoviciAna16Popovici Ana popoviciAna16 Data 2 august 2021 22:55:36
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
using namespace std;
 
ifstream fin ("triang.in");
ofstream fout ("triang.out");
 
int n;
struct punct
{
	long double x, y;
	bool operator < (const punct &alt) const
	{
		if (abs (alt.y - y) < 1e-3)
		{
			if (abs (alt.x - x) < 1e-3)
				return 0;
			return x < alt.x;
		}
		return y < alt.y;
	}
} p[1501];

long double deltax, deltay;
long double cf, l, solx;
punct m;

void calc3 (punct a, punct b, punct &c, punct &d)
{
	
	if (a.y == b.y)
	{
		deltax = b.x - a.x;
		deltay = b.y - a.y;
		l = sqrt(deltax * deltax + deltay * deltay) * sqrt(3) / 2;
		m = {(a.x + b.x)/2, (a.y + b.y)/2};
		c = {m.x, m.y + l};
		d = {m.x, m.y - l};
		
		return;
	}
	
	deltax = b.x - a.x;
	deltay = b.y - a.y;
	cf = deltax / (-deltay);
	l = sqrt(deltax * deltax + deltay * deltay);
	
	solx = sqrt (3 * l * l / (4 * (cf * cf + 1)));
	m = {(a.x + b.x)/2, (a.y + b.y)/2};
	c = {m.x + solx, m.y + solx * cf};
	d = {m.x - solx, m.y - solx * cf};
}

bool cauta (punct &pc)
{
	int st = 1, dr = n, mij;
	while (st <= dr)
	{
		mij = (st+dr)>>1;
		if (pc < p[mij])
			dr = mij - 1;
		else if (p[mij] < pc)
			st = mij + 1;
		else
			return 1;
	}
	return 0;
}

int main()
{
	int i, j;
	punct pu, pd;
	int rasp = 0;
	fin >> n;
	for (i = 1; i<=n; i++)
		fin >> p[i].x >> p[i].y;
	sort(p+1, p+n+1);
	
	for (i = 1; i<=n; i++)
		for (j = i+1; j<=n; j++)
		{
			calc3 (p[i], p[j], pu, pd);
			if (cauta (pu))
				rasp++;
			if (cauta (pd))
				rasp++;
		}
	
	fout << rasp / 3;
	return 0;
}