Cod sursa(job #1020355)

Utilizator ELHoriaHoria Cretescu ELHoria Data 1 noiembrie 2013 22:46:12
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <fstream>
#include <math.h>
#include <algorithm>
#include <functional>
#include <vector>
#define pdd pair<double,double>
#define PI  3.141592653
  
#define x first
#define y second
  
using namespace std;
 
ifstream cin("triang.in");
ofstream cout("triang.out");
  
const double eps = 1e-3;
const double s60 = sin(PI / 3.0);  
const double c60 = cos(PI / 3.0);
const int nmax = 1502;
int n;
pdd v[nmax];
  
inline pdd getPoint(pdd a,pdd b) {
    pdd ret; 
    ret.x = a.x + c60*(b.x - a.x ) - s60*(b.y-a.y);
    ret.y = a.y + s60*(b.x - a.x) + c60 * (b.y - a.y);
    return ret;
}
 
int comp(pdd A, pdd B) {
    if (fabs(A.x - B.x) < eps) {
        if (fabs(A.y - B.y) < eps)
            return 0;
        if (A.y - B.y > eps)
            return 1;
        return -1;
    }
    if (A.x - B.x > eps)
        return 1;
    return -1;
}
  
inline void readData() {
    cin>>n;
    for(int i = 0;i < n;i++) {
        cin>>v[i].x>>v[i].y;
    }
}
  
inline bool search(pdd p) {
    int l = 0, r = n - 1;
    while(l <= r) {
        int mid = (l + r)/2;
        if(comp(v[mid],p) == 0) return 1;
        if(comp(v[mid],p) > 0) r = mid - 1;
        else l = mid + 1;
    }
      
    return 0;
}
  
inline int solve() {
    int ret = 0;
    sort(v,v + n);
    for(int i = 0;i < n;i++) {
        for(int j = i + 1;j < n;j++) {
            ret += search(getPoint(v[i],v[j]));
            ret += search(getPoint(v[j],v[i]));
        }
    }
    ret /= 3;
    return ret;
}
  
int main()
{
    readData();
    cout<<solve()<<"\n";
    return 0;
}