Pagini recente » Cod sursa (job #1751534) | Cod sursa (job #1295611) | Cod sursa (job #262780)
Cod sursa(job #262780)
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef struct {
double x, y;
} Point;
const double e = 1e-3;
const int pa = 1500;
const int pb = 1501;
int N;
Point P[1502];
#define abs(n) ((n < 0) ? (-n) : (n))
bool lt(const Point &a, const Point &b) {
if (abs(a.x - b.x) < e)
return ((b.y - a.y) > e);
return ((b.x - a.x) > e);
}
inline double square(double n) {
return n*n;
}
void calc_points(int i, int j) {
double xm = (P[i].x + P[j].x) / 2.0,
ym = (P[i].y + P[j].y) / 2.0;
double l2 = square(P[i].x - P[j].x) + square(P[i].y - P[j].y);
if (P[j].y - P[i].y < e) {
double dy = sqrt(l2 * (3.0/4.0));
P[pa].x = P[pb].x = xm;
P[pa].y = ym + dy;
P[pb].y = ym - dy;
return;
}
double mp = - (P[j].x - P[i].x) / (P[j].y - P[i].y);
double dx = sqrt(l2 * (3.0 / 4.0) / (1.0 + mp));
double dy = mp*dx;
P[pa].x = xm + dx;
P[pa].y = ym + dy;
P[pb].x = xm - dx;
P[pb].y = ym - dy;
}
void printp(int i) {
printf("%.3lf %.3lf\n", P[i].x, P[i].y);
}
bool avem_echi(int n) {
int nlog, i, l = 0;
for (nlog = 0; (1<<nlog) < N; ++nlog)
;
for (i = nlog; i >= 0; --i)
if ((l + (1<<i) < N) && (P[n].x - P[l + (1<<i)].x > -e)) {
//printf("%.3f\n", P[n].x - P[l+(1<<i)].x);
l += 1<<i;
}
// printf("%d\n", l);
// printp(l);
if ((l >= N) || (P[l].x - P[n].x > e))
return false;
for (i = nlog; i >= 0; --i)
if ((l + (1<<i) < N) && (P[n].y - P[l + (1<<i)].y >= -e))
l += 1<<i;
return (P[l].y - P[n].y <= e);
}
int main(int argc, char *argv[]) {
int i, j, t = 0;
FILE *fi = fopen("triang.in", "r");
fscanf(fi, "%d", &N);
for (i = 0; i < N; ++i)
fscanf(fi, "%lf %lf", &P[i].x, &P[i].y);
fclose(fi);
sort(P, P+N, lt);
for (i = 0; i < N; ++i)
for (j = i+1; j < N; ++j) {
/*printp(i);
printp(j);*/
calc_points(i, j);
/*printp(pa);
printp(pb);
printf("\n");*/
/*if (avem_echi(pa) || avem_echi(pb))
printf("TRIUNGHI ECHILATERAL!\n");
printf("\n");*/
t += avem_echi(pa) + avem_echi(pb);
}
FILE *fo = fopen("triang.out", "w");
fprintf(fo, "%d\n", t/2);
fclose(fo);
return 0;
}