Cod sursa(job #975167)

Utilizator mitrutstrutMitrea Andrei Ionut mitrutstrut Data 19 iulie 2013 12:17:55
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<fstream>
#include<cmath>
#include<set>
#define pdd pair<double,double>
#define EPS 0.001
using namespace std;
int n;
long long sol;
struct Punct{double x,y;};
Punct P[1510],D;
set <pdd> S;
 
inline int Count(Punct A,Punct B)
{
    Punct C;
    pdd c;
    C.x=A.x+D.x*(B.x-A.x)-D.y*(B.y-A.y);
    C.y=A.y+D.y*(B.x-A.x)+D.x*(B.y-A.y);
    c=*S.lower_bound(make_pair(C.x-EPS,C.y-EPS));
    if(fabs(C.x-c.first)<=EPS && fabs(C.y-c.second)<=EPS)
        return 1;
    return 0;
}
 
int main()
{
    int i,j;
    ifstream fin("triang.in");
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>P[i].x>>P[i].y;
        S.insert(make_pair(P[i].x,P[i].y));
    }
    fin.close();
     
    D.x=cos(M_PI/3.0);
    D.y=sin(M_PI/3.0);
    for(i=1;i<=n;i++)
        for(j=i+1;j<=n;j++)
            sol+=1LL*Count(P[i],P[j])+1LL*Count(P[j],P[i]);
    sol/=3LL;
     
    ofstream fout("triang.out");
    fout<<sol<<"\n";
    fout.close();
    return 0;
}