Pagini recente » Winter Challenge 2008 | Cod sursa (job #376348) | Cod sursa (job #1824730) | Cod sursa (job #2029419) | Cod sursa (job #11031)
Cod sursa(job #11031)
#include<fstream.h>
#include<math.h>
struct punct
{
float x,y;
};
punct a[1001];
int i,n,ct=0,mij,st,dr,j,gasit1,gasit2;
float mijx,mijy,dx,dy,x2,x3,y2,y3;
void quick(int p,int q)
{
int i,j,t;
float auxx,auxy;
if(p<q)
{
i=p;
j=q;
t=1;
do
{
if(a[i].x>a[j].x)
{
auxx=a[i].x;
a[i].x=a[j].x;
a[j].x=auxx;
auxy=a[i].y;
a[i].y=a[j].y;
a[j].y=auxy;
t=!t;
}
else
if(a[i].x==a[j].x&&a[i].y>a[j].y)
{
auxx=a[i].x;
a[i].x=a[j].x;
a[j].x=auxx;
auxy=a[i].y;
a[i].y=a[j].y;
a[j].y=auxy;
t=!t;
}
if(t)
j--;
else
i++;
}while(i!=j);
quick(p,i-1);
quick(i+1,q);
}
}
int main()
{
ifstream f("patrate3.in");
ofstream g("patrate3.out");
f>>n;
for(i=1;i<=n;i++)
f>>a[i].x>>a[i].y;
quick(1,n);
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
{
mijx=(a[i].x+a[j].x)/2;
mijy=(a[i].y+a[j].y)/2;
dx=abs(mijx-a[i].x);
dy=abs(mijy-a[i].y);
if(a[i].y<a[j].y)
{
x2=mijx+dy;
y2=mijy-dx;
x3=mijx-dy;
y3=mijy+dx;
}
else
{
x2=mijx-dy;
y2=mijy-dx;
x3=mijx+dy;
y3=mijy+dx;
}
gasit1=1;
st=1;
dr=n;
while(gasit1&&st<dr)
{
mij=(st+dr)/2;
if(a[mij].x==x2&&a[mij].y==y2)
gasit1=0;
else
if(a[mij].x<=x2)
st=mij+1;
else
dr=mij-1;
}
if(gasit1==0)
{
gasit2=1;
st=1;
dr=n;
while(gasit2&&st<dr)
{
mij=(st+dr)/2;
if(a[mij].x==x3&&a[mij].y==y3)
gasit2=0;
else
if(a[mij].x>=x3)
st=mij+1;
else
dr=mij-1;
}
}
if(gasit1==0&&gasit2==0)
ct++;
}
g<<ct;
//for(i=1;i<=n;i++)
//g<<a[i].x<<" "<<a[i].y<<'\n';
return 0;
}