Pagini recente » Cod sursa (job #1136846) | Cod sursa (job #1204321) | Cod sursa (job #1773816) | Cod sursa (job #1498524) | Cod sursa (job #382121)
Cod sursa(job #382121)
#include <iostream>
#include <fstream>
#include <math.h>
//#include <conio.h>
using namespace std;
#define e 0.000001
int N;
struct Pct {
double x;
double y;
} vec[1501];
int cmp(Pct a, Pct b) {
if(a.x!=b.x) { return a.x<b.x; }
return a.y<b.y;
}
int CBinar(double x, double y, int poz) {
int ls=0, ld=N-1, mij;
while(ls<=ld) {
if(ld<poz) { return 0; }
mij=ld+(ls-ld)/2;
if(-e<=vec[mij].x-x && vec[mij].x-x<e && -e<=vec[mij].x-x && vec[mij].y-y<e) {
return mij;
}
else if(vec[mij].x<x) {
//caut in dreapta
ls=mij+1;
}
else if(vec[mij].x>x) {
//caut in stinga
ld=mij-1;
}
else if(vec[mij].x==x && vec[mij].y<y) {
ls=mij+1;
}
else if(vec[mij].x==x && vec[mij].y>y) {
ld=mij-1;
}
}
return 0;
}
int main() {
FILE *f1=fopen("triang.in", "r"), *f2=fopen("triang.out", "w");
int i, j, nr=0, la, lu;
double p, q, x, y, z;
double a, b, c, d;
double aux1, aux2, aux3, del, rad, y1, y2, x1, x2;
fscanf(f1, "%d", &N);
for(i=0; i<N; i++) {
fscanf(f1, "%lf%lf", &vec[i].x, &vec[i].y);
}
sort(vec, vec+N, cmp);
for(i=0; i<N; i++) {
for(j=i+1; j<N; j++) {
a = vec[i].x; b = vec[i].y;
c = vec[j].x; d = vec[j].y;
if(a-c!=0 && b-d!=0) {
p=2*(a-c);
p=(a+c)/2 + (b+d)*(b-d)/p;
q=(b-d)/(a-c);
//x+q*y=p
z = c*c - 2*a*c + d*d - 2*b*d;
aux1 = q*q + 1;
aux2 = 2*a*q - 2*b - 2*p*q;
aux3 = p*p - 2*a*p - z;
//aux1 * y^2 + aux2 * y + aux3 = 0
del=aux2*aux2 - 4*aux1*aux3;
del=sqrt(del);
if(-e<=(-aux2-del) && (-aux2-del)<e) { y1=0; }
else { y1=(-aux2-del)/(2*aux1); }
if(-e<=(p-q*y1) && (p-q*y1)<e) { x1=0; }
else { x1=p-q*y1; }
if(-e<=(del-aux2) && (del-aux2)<e) { y2=0; }
else { y2=(-aux2+del)/(2*aux1); }
if(-e<=(p-q*y2) && (p-q*y2)<e) { x2=0; }
else { x2=p-q*y2; }
}
else if(b-d==0) {
x1=x2=(a+c)/2;
aux1=1;
aux2=-2*b;
aux3=(c-a)*(c-a)/4 + b*b - (a-c)*(a-c);
del=aux2*aux2 - 4*aux1*aux3;
del=sqrt(del);
if(-e<=(-aux2-del) && (-aux2-del)<e) { y1=0; }
else { y1=(-aux2-del)/(2*aux1); }
if(-e<=(del-aux2) && (del-aux2)<e) { y2=0; }
else { y2=(-aux2+del)/(2*aux1); }
}
else if(a-c==0) {
y1=y2=(b+d)/2;
aux1=1;
aux2=-2*c;
aux3=(b-d)*(b-d)/4 + c*c - (b-d)*(b-d);
del=aux2*aux2 - 4*aux1*aux3;
del=sqrt(del);
if(-e<=(-aux2-del) && (-aux2-del)<e) { y1=0; }
else { x1=(-aux2-del)/(2*aux1); }
if(-e<=(del-aux2) && (del-aux2)<e) { y2=0; }
else { x2=(-aux2+del)/(2*aux1); }
}
la=CBinar(x1, y1, j);
lu=CBinar(x2, y2, j);
//cout<<"i="<<i<<" , j="<<j<<endl;
//cout<<x1<<" "<<y1<<endl;
//cout<<x2<<" "<<y2<<endl;
//cout<<la<<", "<<lu<<endl;
//cout<<endl;
if(la && la>j) { nr++; }
if(lu && lu>j) { nr++; }
}
}
fprintf(f2, "%d\n", nr);
fclose(f1); fclose(f2);
//getch();
return 0;
}