Cod sursa(job #3361801)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 28 iulie 2026 17:23:23
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
// Ilie "The-Winner" Dumitru
// Dumnezeu sa o ierte
#include<bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define err(...) fprintf(stderr, __VA_ARGS__)
using ll=long long;
using dbl=long double;
constexpr int NMAX=1'505;
constexpr ll MOD=1'000'000'007;
constexpr dbl EPS=0.001L;

struct pct
{
	dbl x, y;
};

int N;
pct p[NMAX];
dbl d[NMAX];
int o[NMAX];
dbl dst[NMAX][NMAX];

dbl dist(pct a, pct b)
{
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

int count()
{
	int i, j, k, ans=0;

	std::sort(p, p+N, [](pct a, pct b) {return a.x<b.x || (a.x==b.x && a.y<b.y);});
	for(i=0;i<N;++i)
	{
		o[i]=i;
		for(j=0;j<N;++j)
			dst[i][j]=dist(p[i], p[j]);
	}

	for(i=0;i+2<N;++i)
	{
		for(j=i;j<N;++j)
			d[o[j]]=dst[i][o[j]];

		std::sort(o+i, o+N, [&](int a, int b) {
			if(fabsl(d[a]-d[b])<EPS)
				return p[a].y<p[b].y;
			return d[a]<d[b];
		});

		for(j=i+1, k=i+2;j<N && k<N;)
		{
			k=std::max(k, j+1);
			if(fabsl(d[o[j]]-d[o[k]])>=EPS)
				++j;
			else if(fabsl(dst[o[j]][o[k]]-d[o[j]])<EPS)
			{
				++ans;
				++j;
			}
			else if(dst[o[j]][o[k]]>d[o[j]])
				++j;
			else
				++k;
		}
	}

	return ans;
}

int main()
{
	FILE* f=fopen("triang.in", "r"), *g=fopen("triang.out", "w");
	int i;

	fscanf(f, "%d", &N);
	for(i=0;i<N;++i)
		fscanf(f, "%Lf%Lf", &p[i].x, &p[i].y);

	fprintf(g, "%d\n", count());

	fclose(f);
	fclose(g);
	return 0;
}