Pagini recente » Cod sursa (job #1328695) | Cod sursa (job #314128) | Cod sursa (job #163279) | Cod sursa (job #450781) | Cod sursa (job #4419)
Cod sursa(job #4419)
/*
#INFOARENAAA
*/
#include <stdio.h>
#include <math.h>
int n, sol = 0;
double eps = 0.001;
struct point {double x, y;};
point v[1600];
void read_in() {
freopen("triang.in", "r", stdin);
scanf("%d", &n);
for (int i=1; i<=n; i++) scanf("%lf %lf", &(v[i].x), &(v[i].y));
fclose(stdin);
}
double dist(point A, point B) {
return 3.0/4.0*((A.x-B.x)*(A.x-B.x) + (A.y - B.y)*(A.y - B.y));
}
point solve( double M, double D) {
point ret;
ret.x = sqrt(D / (M*M + 1));
ret.y = M*ret.x;
return ret;
}
double abs(double A) {
if (A < 0) return -A;
return A;
}
void print_out() {
freopen("triang.out", "w", stdout);
printf("%d\n", sol);
fclose(stdout);
}
int k, l ,r, pasi=0;
int mai_mic(point A, point B) {
if (A.x > B.x) return 1;
if (A.x == B.x && A.y > B.y) return 1;
return 0;
}
int partite(int p, int r) {
point x = v[p];
int i = p - 1, j= r+1;
while (1) {
do {j--; } while (mai_mic(v[j], x));
do {i++;} while (mai_mic(x, v[i]));
if (i < j) {point aux = v[i]; v[i] = v[j]; v[j] = aux;}
else return j;
}
}
void qsort(int p, int r) {
if (p < r) {
int q = partite(p ,r);
qsort(p, q);
qsort(q+1, r);
}
}
int main() {
read_in();
int i, j;
//hai sa le sortam
qsort(1, n);
for (i=1; i<=n; i++)
for (j=i+1; j<=n; j++) {
double M;
point middle, raise, p;
middle.x = v[i].x + v[j].x; middle.x/=2;
middle.y = v[i].y + v[j].y; middle.y/=2;
if (abs(v[i].y - v[j].y)<eps) {
raise.x = 0; raise.y = sqrt(dist(v[i], v[j]));
}
else {
M =-(v[i].x - v[j].x)/(v[i].y - v[j].y);
raise = solve(M, dist(v[i], v[j]));}
int gasit = 0;
p.x = middle.x + raise.x;
p.y = middle.y + raise.y;
l = j ; r = n;
if (!(p.x > v[n].x+eps))
while (l<=r) {
k = l +r; k>>=1;
if (abs(v[k].x - p.x) < eps) {
if( abs(v[k].y - p.y) < eps) {gasit = 1; break;}
if (p.y > v[k].y) l = k + 1;
else r = k - 1;
}
else {if (p.x > v[k].x) l= k+1; else r = k-1;}
}
//cauta binar si pune gasit = 1 daca gasesti
sol+=gasit; gasit = 0;
raise.x*=-1; raise.y*=-1;
p.x = middle.x + raise.x;
p.y = middle.y + raise.y;
l = j ; r = n;
pasi=0;
if ( ! (p.x > v[n].x+eps))
while (l<=r) {
k = l +r; k>>=1;
if (abs(v[k].x - p.x) < eps) {
if( abs(v[k].y - p.y) < eps) {gasit = 1; break;}
if (p.y > v[k].y) l = k + 1;
else r = k - 1;
}
else {if (p.x > v[k].x) l= k +1; else r = k-1;}
}
//cauta binar si pune gasit =1 daca gasesti
sol+=gasit;
}
print_out();
return 0;
}