Cod sursa(job #2907827)

Utilizator Bogdy_PPrunescu Bogdan Bogdy_P Data 31 mai 2022 17:53:09
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include<bits/stdc++.h>
# define M_PI 3.14159265358979323846
double eps = 0.0001;
using namespace std;
unordered_multimap<double, double>mp;
double s60 = sin(60 * M_PI / 180.0);
double c60 = cos(60 * M_PI / 180.0);
double xp, yp;
int i, j, k, n,nrt;
struct point
{
	double x;
	double y;
}p[1600];
bool compare(point a, point b)
{
	if (a.x == b.x)
		return a.y < b.y;
	return a.x < b.x;
}
int cb(int in, int sf, double x, double y)
{
	while (in <= sf)
	{
	   int mid = (in + sf)/2;
	   if ((abs(p[mid].x - x) < eps)&&(abs(p[mid].y - y) < eps))
		   return 1;
	   else
	   {
		   if (p[mid].x < x)
			   in = mid+1;
		   else
			   sf = mid-1;
	   }
	}
	return 0;
}
int main()
{
	ifstream f("triang.in");
	ofstream g("triang.out");
	f >> n;
	for (i = 1; i <= n; i++)
	{
		f >> xp >> yp;
		mp.insert(make_pair(xp, yp));
		p[i].x = xp;
		p[i].y = yp;
	}
	sort(p + 1, p + n + 1, compare);
	for(i=1;i<=n-2;i++)
		for(j=i+1;j<=n-1;j++)
			{
				xp = c60*(p[i].x + p[j].x) + s60*(p[i].y - p[j].y);
				yp = s60*(p[j].x - p[i].x) + c60*(p[j].y + p[i].y);
				nrt+=cb(j + 1, n, xp, yp);
				xp = c60*(p[i].x + p[j].x) + s60*(p[j].y - p[i].y);
				yp = s60*(p[i].x - p[j].x) + c60*(p[j].y + p[i].y);
				nrt += cb(j + 1, n, xp, yp);
			}
	g << nrt;
	return 0;
}