Pagini recente » Cod sursa (job #676007) | Cod sursa (job #1187256) | Cod sursa (job #2579979) | Cod sursa (job #205660) | Cod sursa (job #1017948)
#include<iostream>
#include<fstream>
#include<ctime>
#include<cstdlib>
#include<cmath>
using namespace std;
float pa[500000];
float pivot(int left, int right)
{
float p1,p2,p3,p,mini,maxi;
p1=pa[left + rand() % (right-left+1)];
p2=pa[left + rand() % (right-left+1)];
p3=pa[left + rand() % (right-left+1)];
if(p1<=p2&&p1<=p3)
mini=p1;
if(p2<=p1&&p2<=p3)
mini=p2;
if(p3<=p1&&p3<=p2)
mini=p3;
if(p1>=p2&&p1>=p3)
maxi=p1;
if(p2>=p1&&p2>=p3)
maxi=p2;
if(p3>=p1&&p3>=p2)
maxi=p3;
p=p1+p2+p3-maxi-mini;
return p;
}
void quicksort(int left, int right)
{
int i=left, j=right, tmp;
float piv;
float tmpd;
piv=pivot(left,right);
while(i<=j)
{
while(pa[i]<piv)
i++;
while(pa[j]>piv)
j--;
if(i<=j)
{
tmpd=pa[i];
pa[i]=pa[j];
pa[j]=tmpd;
i++;
j--;
}
}
if(left<j)
quicksort(left,j);
if(i<right)
quicksort(i,right);
}
int main()
{
ifstream f("trapez.in");
ofstream g("trapez.out");
int n, i, k, nr, j,aa,u, v, bb, d;
long x[1001], y[1001], s;
f>>n;
for(i=0;i<n;i++)
f>>x[i]>>y[i];
k=0;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
{
if(y[j]==y[i])
pa[k]=0;
else if(x[j]==x[i])
pa[k]=100;
else{
if(x[j]>x[i] && y[j]>y[i])
pa[k]=atan2(x[j]-x[i], y[j]-y[i]);
if(x[j]<x[i] && y[j]<y[i])
pa[k]=atan2(x[i]-x[j], y[i]-y[j]);
if(x[j]>x[i] && y[j]<y[i])
pa[k]=atan2(x[j]-x[i], y[j]-y[i]);
if(x[j]<x[i] && y[j]>y[i])
pa[k]=atan2(x[i]-x[j], y[i]-y[j]);}
k++;
}
quicksort(0, k-1);
s=0;
nr=1;
for(i=1;i<k;i++)
{
if(pa[i]==pa[i-1]){
nr++;}
else
{
s+=nr*(nr-1)/2;
nr=1;
}
}
s+=nr*(nr-1)/2;
g<<s;
}