Pagini recente » Cod sursa (job #240020) | Cod sursa (job #1698511) | Cod sursa (job #804341) | Cod sursa (job #594073) | Cod sursa (job #1592251)
#include <iostream>
#include <fstream>
#include <math.h>
#include <iomanip>
#include <algorithm>
#define EPS 0.001
using namespace std;
ifstream in("triang.in");
ofstream out("triang.out");
const double sin60 = sin(60*M_PI/180);
const double cos60 = cos(60*M_PI/180);
const double sin60N = sin(-60*M_PI/180);
const double cos60N = cos(-60*M_PI/180);
struct p {
double x;
double y;
};
int n;
p v[1501];
p t;
double fabs (double a)
{
if (a<0)
return -a;
return a;
}
int check (p a,p b)
{
if (fabs (a.x-b.x)<EPS)
{
if (fabs (a.y-b.y)<EPS)
return 0;
else if (a.y>b.y)
return -1;
else
return 1;
}
else if(a.x>b.x)
return -1;
else
return 1;
}
bool eq(double a, double b) {
return ((int)a*1000) == ((int)b*1000);
}
p rot60(p p1, p p2) {
int mult = 1;
if(p2.y < p1.y)
mult *= -1;
t.x = p1.x + (p2.x - p1.x) * cos60 - (p2.y - p1.y) * mult * sin60;
t.y = p1.y + (p2.x - p1.x) * sin60 + (p2.y - p1.y) * mult * cos60;
return t;
}
p rot60N(p p1, p p2) {
int mult = 1;
if(p2.y < p1.y)
mult *= -1;
t.x = p1.x + (p2.x - p1.x) * cos60N - (p2.y - p1.y) * mult * sin60N;
t.y = p1.y + (p2.x - p1.x) * sin60N + (p2.y - p1.y) * mult * cos60N;
return t;
}
bool cmp(p t1, p t2) {
if(t1.x == t2.x)
return t1.y < t2.y;
return t1.x < t2.x;
}
bool caut(p t1, int st, int dr) {
int mid = (st+dr)/2;
if(st >= dr)
return false;
int ch = check(v[mid], t1);
if(ch < 0)
return caut(t1, mid+1, dr);
if(ch > 0)
return caut(t1, st, mid-1);
return true;
//return true;
}
int main() {
in >> n;
for(int i = 0; i < n; i++) {
in >> t.x >> t.y;
v[i] = t;
}
sort(v, v+n, cmp);
/*for(int i = 0; i < n; i++) {
cout << v[i].x << " " << v[i].y << endl;
}*/
long long rez = 0;
for(int i = 0; i < n-1; i++) {
for(int j = i+1; j < n; j++) {
t.x=(v[j].x-v[i].x)*cos60-(v[j].y-v[i].y)*sin60+v[i].x;
t.y=(v[j].x-v[i].x)*sin60+(v[j].y-v[i].y)*cos60+v[i].y;
rez+= caut(t, 0, n);
t.x=(v[i].x-v[j].x)*cos60-(v[i].y-v[j].y)*sin60+v[j].x;
t.y=(v[i].x-v[j].x)*sin60+(v[i].y-v[j].y)*cos60+v[j].y;
rez+= caut(t, 0, n);
//double p1 =
//cout << "(" << v1[i] << ", " << v2[i] << ") (" << v1[j] << ", " << v2[j] << ") -> " << "(" << hF11 << ", " << hF12 << ") (" << hF21 << ", " << hF22 << ")" << endl;
}
}
out << rez/3;
return 0;
}