Cod sursa(job #2742601)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 21 aprilie 2021 11:43:26
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#include <math.h>

#define nozerous(x) (x & -x)
#define MOD 30103
#define M_PI           3.14159265358979323846
#define EPS 0.0001
using namespace std;

const int INF = (1 << 30), NMAX(1505);
using VI  = vector<int>;
using VVI = vector<VI>;
using VB  = vector<bool>;
using Point = array<int, 2>;

void BUNA(const string& task = "")
{
    if (!task.empty())
        freopen((task + ".in").c_str(), "r", stdin),
                freopen((task + ".out").c_str(), "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
void PA()
{
    exit(0);
}

struct pnct{
    double x, y;
}v[NMAX];

inline bool cmp1(pnct a, pnct b){
    if(abs(a.x - b.x) < EPS)
        return a.y < b.y;
    return a.x < b.x;
}
pnct vertex(pnct p1, pnct p2){
  double s60 = sin(60 * M_PI / 180.0);
  double c60 = cos(60 * M_PI / 180.0);

  pnct v = {
    c60 * (p1.x - p2.x) - s60 * (p1.y - p2.y) + p2.x,
    s60 * (p1.x - p2.x) + c60 * (p1.y - p2.y) + p2.y
  };

  return v;
}

int main()
{
    BUNA("triang");
    int n;
    cin >> n;

    for(int i = 1; i <= n; ++i)
        cin >> v[i].x >> v[i].y;

    sort(v + 1, v + n + 1, cmp1);

    int nr = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            if(i != j)
            {
                auto xx = vertex(v[i], v[j]);
                int st = 1;
                int dr = n;
                while(st <= dr){
                    int mij = (st + dr) / 2;
                    if(abs(v[mij].x - xx.x) < EPS){
                        if(abs(v[mij].y - xx.y) < EPS){
                            ++nr;
                            break;
                        }
                        else if(v[mij].y < xx.y)
                            st = mij + 1;
                        else dr = mij - 1;
                    }
                    else if(v[mij].x < xx.x)
                        st = mij + 1;
                    else dr = mij - 1;
                }
            }
    cout << nr / 3 << '\n';
    PA();
}