Pagini recente » Cod sursa (job #1948265) | Cod sursa (job #2391876) | Cod sursa (job #2174677) | Cod sursa (job #928437) | Cod sursa (job #382102)
Cod sursa(job #382102)
#include <iostream>
#include <fstream>
#include <math.h>
//#include <conio.h>
using namespace std;
#define e 0.001
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) {
mij=(ls+ld)/2;
if(vec[mij].x-x<e && 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() {
fstream f1, f2;
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;
f1.open("triang.in", ios::in);
f1>>N;
for(i=0; i<N; i++) {
f1>>vec[i].x>>vec[i].y;
}
f1.close();
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(-aux2-del<e) { y1=0; }
else { y1=(-aux2-del)/(2*aux1); }
if(p-q*y1<e) { x1=0; }
else { x1=p-q*y1; }
if(del-aux2<e) { y2=0; }
else { y2=(-aux2+del)/(2*aux1); }
if(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(-aux2-del<e) { y1=0; }
else { y1=(-aux2-del)/(2*aux1); }
if(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(-aux2-del<e) { y1=0; }
else { x1=(-aux2-del)/(2*aux1); }
if(del-aux2<e) { y2=0; }
else { x2=(-aux2+del)/(2*aux1); }
}
//else { } blabla
//(x1, y1); (x2, y2);
//cout<<x1<<" "<<y1<<" , "<<x2<<" "<<y2<<endl;
//cout<<CBinar(x1, y1, j)<<" "<<CBinar(x2, y2, j)<<endl;
//cout<<endl;
la=CBinar(x1, y1, j);
lu=CBinar(x2, y2, j);
if(la && la>j) { nr++; }
if(lu && lu>j) { nr++; }
}
}
f2.open("triang.out", ios::out);
f2<<nr<<endl;
f2.close();
//getch();
return 0;
}