Cod sursa(job #1768972)

Utilizator MickeyTurcu Gabriel Mickey Data 1 octombrie 2016 19:23:25
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include<fstream>
#include<string.h>
#include<ctype.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<array>
#include<deque>
#include<math.h>
#include<unordered_set>
#include<set>
#include<iomanip>
#include<bitset>
# 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");
	//ifstream f("file.in");
	//ofstream g("file.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;
}