Pagini recente » Cod sursa (job #2030280) | Cod sursa (job #2020725) | Cod sursa (job #672070) | Cod sursa (job #1858332) | Cod sursa (job #130106)
Cod sursa(job #130106)
#include <cstdio>
using namespace std;
template < typename T >
void heap_shift (T * a, int start, int count) {
int root, child;
T aux;
root = start;
while ((child = 2 * root + 1) < count) {
if (child < count - 1 && a [child] < a [child + 1]) ++ child;
if (a [root] < a [child]) {
aux = a [root]; a [root] = a [child]; a [child] = aux;
root = child;
} else return;
}
}
template < typename T >
void heap_sort (T * a, int count) {
int start, end;
T aux;
start = count / 2 - 1; end = count - 1;
while (start >= 0) {
heap_shift (a, start, count);
-- start;
}
while (end > 0) {
aux = a [0]; a [0] = a [end]; a [end] = aux;
heap_shift (a, 0, end);
-- end;
}
}
typedef long long int bigint;
class dreapta {
public:
inline void initializeaza(int x1, int y1, int x2, int y2) {
if(x2 >= x1) {
dx_ = x2-x1; dy_=y2-y1;
} else {
dx_ = x1-x2; dy_=y1-y2;
}
}
inline bool operator < (dreapta const & d) const {
if(0 == dx_) {
if(0 != d.dx_) return true;
return false;
} else {
if(0 == d.dx_) return true;
bigint s1, s2;
s1=dy_; s1 *= d.dx_;
s2=d.dy_; s2 *= dx_;
if(s1<s2) return true;
return false;
}
}
inline bool operator == (dreapta const & d) const {
if(0 == dx_) {
if(0 != d.dx_) return false;
return true;
} else {
if(0 == d.dx_) return false;
bigint s1, s2;
s1=dy_; s1 *= d.dx_;
s2=d.dy_; s2 *= dx_;
if(s1==s2) return true;
return false;
}
}
private:
int dx_, dy_;
};
struct punct {
int x, y;
};
int const MAXN = 1000;
dreapta v[(MAXN * (MAXN-1))/2]; // comb
punct p[MAXN];
int main() {
int n, m, i, j, num, sum;
FILE * io;
io = fopen ("trapez.in", "r");
setvbuf(io, NULL, _IOFBF, 1024 * 1024);
fscanf(io, "%d", &n);
for(i=0;i<n;i++) {
fscanf(io, "%d %d", &p[i].x, &p[i].y);
}
for(i=0, m=0;i<n;i++) {
for(j=i+1;j<n;j++) {
v[m].initializeaza(p[i].x, p[i].y, p[j].x, p[j].y);
++ m;
}
}
fclose(io);
heap_sort < dreapta > (v, m);
for(i=1, num=0, sum=0;i<m;i++) {
if(v[i]==v[i-1]) {
++ num;
} else {
sum += (num * (num-1))/2; // comb
num = 1;
}
}
sum += (num * (num-1))/2;
io = fopen("trapez.out", "w");
fprintf(io, "%d\n", sum);
fclose(io);
return 0;
}