Cod sursa(job #2766703)

Utilizator popoviciAna16Popovici Ana popoviciAna16 Data 2 august 2021 22:19:50
Problema Triang Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
using namespace std;
 
ifstream fin ("triang.in");
ofstream fout ("triang.out");
	
const long double pi = 3.1415926535897932384626433832795;
 
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];
	
void calc3 (punct a, punct b, punct &c, punct &d)
{
	punct ba;
	long double r, alfa;
	
	ba.x = b.x - a.x;
	ba.y = b.y - a.y;
	
	r = sqrt (ba.x * ba.x + ba.y * ba.y);
	alfa = acos (ba.x / r);
	
	c.x = r * cos (alfa + pi/3) + a.x;
	c.y = r * sin (alfa + pi/3) + a.y;
	
	d.x = r * cos (alfa - pi/3) + a.x;
	d.y = r * sin (alfa - pi/3) + a.y;
}

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;
}