Cod sursa(job #216931)
#include<fstream>
#include<cstdlib>
using namespace std;
struct punct{
int x,y;
};
punct a[1001];
int p1[500501];
int p2[500501];
int n,np;
int nR(int st,int dr){
double x1=p1[st];
if(p2[st]) x1=x1/p2[st];
else {
if(p2[dr]) return 1;
else return 0;
}
double x2=p1[dr];
if(p2[dr]) x2=x2/p2[dr];
else return 0;
if(x1>x2) return 1;
else return 0;
}
int part(int st,int dr){
int ii, jj, aux;
ii=0;jj=-1;
while(st<dr){
if(nR(st,dr)){
aux=-ii;
ii=-jj;
jj=aux;
aux=p1[st];p1[st]=p1[dr];p1[dr]=aux;
aux=p2[st];p2[st]=p2[dr];p2[dr]=aux;
}
st+=ii;dr+=jj;
}
return st;
}
void sorteaza(int st,int dr){
if(st<dr){
int r=random()%(dr-st+1);
r=st+r;
int aux;
aux=p1[r];p1[r]=p1[st];p1[st]=aux;
aux=p2[r];p2[r]=p2[st];p2[st]=aux;
int m=part(st,dr);
sorteaza(st,m-1);
sorteaza(m+1,dr);
}
}
int main(){
int i,j;
ifstream f("trapez.in");
f>>n;
for(i=0;i<n;i++)
f>>a[i].x>>a[i].y;
f.close();
for(i=0;i<n;i++)
for(j=i+1;j<n;j++){
p1[np]=a[i].y-a[j].y;
p2[np]=a[i].x-a[j].x;
np++;
}
sorteaza(0,np-1);
int rasp=0;
int comp1=p1[0],comp2=p2[0],k=1;
for(i=1;i<np;i++){
if(comp1*p2[i]==comp2*p1[i]) k++;
else{
rasp+=(k*(k-1)/2);
comp1=p1[i];comp2=p2[i];
k=1;
}
}
ofstream g("trapez.out");
g<<rasp<<'\n';
g.close();
return 0;
}