Cod sursa(job #2146258)

Utilizator amarghescuAnton Marghescu amarghescu Data 27 februarie 2018 21:33:53
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include<cstdio>
#include<algorithm>
#include<vector>
#define eps 1e-3
using namespace std;
pair<double,double>v[1505];
vector<pair<double,int> >pct[1505];
int main(){
freopen("triang.in","r",stdin);
freopen("triang.out","w",stdout);
int n,i,j,st,dr,mij;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%lf%lf",&v[i].first,&v[i].second);
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++){
double dist=sqrt((double)(v[i].first-v[j].first)*(v[i].first-v[j].first)+(double)(v[i].second-v[j].second)*(v[i].second-v[j].second));
pct[i].push_back(make_pair(dist,j));
pct[j].push_back(make_pair(dist,i));}
for(i=1;i<=n;i++)
sort(pct[i].begin(),pct[i].end());
long long rasp=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if (i!=j){
double dist=sqrt((double)(v[i].first-v[j].first)*(v[i].first-v[j].first)+(double)(v[i].second-v[j].second)*(v[i].second-v[j].second));
st=0;
dr=n-2;
while(st<=dr){
mij=(st+dr)/2;
if (pct[i][mij].first<dist && pct[j][mij].first>dist)
break;
if (pct[i][mij].first>dist && pct[j][mij].first<dist)
break;
if (pct[i][mij].first<dist && pct[j][mij].first<dist){
st=mij+1;
continue;}
if (pct[i][mij].first>dist && pct[j][mij].first>dist){
dr=mij-1;
continue;}
if (abs(pct[i][mij].first-dist)<eps){
if (pct[j][mij].first<dist){
st=mij+1;
continue;}
if (pct[j][mij].first>dist){
dr=mij-1;
continue;}
if (abs(pct[j][mij].first-dist)<eps){
rasp++;
if (mij)
if (abs(pct[i][mij-1].first-dist)<eps && abs(pct[j][mij-1].first-dist)<eps)
rasp++;
if (mij<n-2)
if (abs(pct[i][mij+1].first-dist)<eps && abs(pct[j][mij+1].first-dist)<eps)
rasp++;
break;}}
if (abs(pct[j][mij].first-dist)<eps){
if (pct[i][mij].first<dist){
st=mij+1;
continue;}
if (pct[i][mij].first>dist){
dr=mij-1;
continue;}
if (abs(pct[i][mij].first-dist)<eps){
rasp++;
if (mij)
if (abs(pct[i][mij-1].first-dist)<eps && abs(pct[j][mij-1].first-dist)<eps)
rasp++;
if (mij<n-2)
if (abs(pct[i][mij+1].first-dist)<eps && abs(pct[j][mij+1].first-dist)<eps)
rasp++;
break;}}}
rasp--;}
printf("%lld\n",rasp/6);
return 0;}