Pagini recente » Cod sursa (job #1161929) | Statistici Dolocan Georgiana Elena (GeorgianaElena) | Cod sursa (job #528767) | Cod sursa (job #1635637) | Cod sursa (job #1452293)
#include <stdio.h>
#include <math.h>
#define MAXN 1500
#define EPS 0.001
#define INF 2000000000
typedef struct{
double x, y;
}punct;
int point[MAXN];
punct v[MAXN];
inline char cmp(punct a, punct b){
if(a.x - b.x < -EPS)
return 0;
if(a.x - b.x > EPS)
return 2;
if(a.y - b.y < -EPS)
return 0;
if(a.y - b.y > EPS)
return 2;
return 1;
}
void qs(int st, int dr){
int i = st, j = dr, aux;
punct pi;
pi.x = v[point[(st + dr) / 2]].x;
pi.y = v[point[(st + dr) / 2]].y;
while(i <= j){
while(cmp(pi, v[point[i]]) == 2)
i++;
while(cmp(v[point[j]], pi) == 2)
j--;
if(i <= j){
aux = point[i]; point[i] = point[j]; point[j] = aux;
i++; j--;
}
}
if(st < j)
qs(st, j);
if(i < dr)
qs(i, dr);
}
inline punct lipsa(punct a, punct b){
punct rez;
double f, g, l = sqrt((a.y - b.y) * (a.y - b.y) + (a.x - b.x) * (a.x - b.x)), h = l * sqrt(3) / 2, dx;
if(a.y == b.y){
rez.x = -INF;
rez.y = -INF;
}
else if(a.x == b.x){
rez.x = (a.x + b.x) / 2;
rez.y = h;
}
else{
f = -(b.x - a.x) / (b.y - a.y);
dx = sqrt((h * h) / (f * f + 1));
rez.x = (a.x + b.x) / 2 + dx;
rez.y = (a.y + b.y) / 2 + dx * f;
if(cmp(b, rez) == 2){
rez.x = (a.x + b.x) / 2 - dx;
rez.y = (a.y + b.y) / 2 - dx * f;
if(cmp(b, rez) == 2){
rez.x = -INF;
rez.y = -INF;
}
}
}
return rez;
}
inline char caut(int st, int dr, punct a){
int i = st - 1, pas = 1 << 10;
while(pas > 0){
if(i + pas <= dr && cmp(a, v[point[i + pas]]) == 2)
i += pas;
pas >>= 1;
}
if(i < dr && cmp(a, v[point[i + 1]]) == 1)
return 1;
return 0;
}
int main(){
FILE *in = fopen("triang.in", "r");
int n, i;
fscanf(in, "%d", &n);
for(i = 0; i < n; i++){
fscanf(in, "%lf%lf", &v[i].x, &v[i].y);
point[i] = i;
}
fclose(in);
qs(0, n - 1);
int j, rez = 0;
punct x;
for(i = 0; i < n; i++){
for(j = i + 1; j < n; j++){
x = lipsa(v[point[i]], v[point[j]]);
if(!(x.x == -INF && x.y == -INF))
rez += caut(j + 1, n - 1, x);
}
}
FILE *out = fopen("triang.out", "w");
fprintf(out, "%d", rez);
fclose(out);
return 0;
}