Cod sursa(job #2626265)

Utilizator Katherine456719Swan Katherine Katherine456719 Data 6 iunie 2020 12:57:11
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <bits/stdc++.h>
#include <fstream>
#include <algorithm>
#include <vector>

#define PI 3.14159265
using namespace std;
ifstream f("triang.in");
ofstream g("triang.out");
typedef long double ld;
int n,ans=0;
pair<ld,ld> v[10005];
void cautare(ld x,ld y,int j)
{
    int r=0;
    for(int p=10; p>=0; p--)
        if(r+(1<<p)<=n and (v[r+(1<<p)].first<x or ((abs(v[r+(1<<p)].first - x) < 1e-3 and abs(y-v[r+(1<<p)].second) < 1e-3))))
            r+=(1<<p);
    if(abs(v[r].first - x) < 1e-3 and abs(v[r].second-y) <1e-3 and j<r)
        ans++;
}
int main()
{
    f>>n;
    for(int i=1; i<=n; i++)
    {
        ld x,y;
        f>>x>>y;
        v[i]= {x,y};
    }
    sort(v+1,v+n+1);
    for(int i=1; i<n; i++)
        for(int j=i+1; j<=n; j++)
        {

            ld difx= v[j].first - v[i].first;
            ld dify= v[j].second - v[i].second;

            ld unghi = PI / 3;
            ld rotx = difx * cos(unghi) - dify * sin(unghi);
            ld roty = difx * sin(unghi) + dify * cos(unghi);

            ld x = rotx + v[i].first;
            ld y = roty + v[i].second;

            if((x!=v[i].first or y!=v[i].second) and (x!=v[j].first or y!=v[j].second))
                cautare(x,y,j);

            unghi = -PI / 3;
            rotx = difx * cos(unghi) - dify * sin(unghi);
            roty = difx * sin(unghi) + dify * cos(unghi);

            x= rotx + v[i].first;
            y= roty + v[i].second;

            if((x!=v[i].first or y!=v[i].second) and (x!=v[j].first or y!=v[j].second))
                cautare(x,y,j);
        }
    g<<ans;
    return 0;
}