Cod sursa(job #2616800)

Utilizator AndreiStanescuAlloys Nokito AndreiStanescu Data 19 mai 2020 23:39:42
Problema Patrate 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 8.59 kb
//Patrate3
#include<bits/stdc++.h>
#define prec 1e-5
#define N 10002
using namespace std;
int n;
struct coord{
    double x,y;
}p[N];

bool comp(coord A,coord B)
{
    if(B.x-A.x>=prec)
        return 1;
    if(fabs(A.x-B.x)<prec)
        if(A.y<=B.y-prec)
            return 1;
    return 0;
}

bool binary_search(int i,int j,double x,double y)
{
    int l=i;
    int r=j;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(fabs(p[mid].x-x)<=prec){
            if(fabs(p[mid].y-y)<=prec)
                return 1;
            else if(p[mid].y < y)
                l=mid+1;
            else
                r=mid-1;
        }
        else
            if(p[mid].x<x)
                l=mid+1;
        else
            r=mid-1;
    }
    return 0;
}

void read()
{
    ifstream fin("patrate3.in");
    ofstream fout("patrate3.out");
    fin>>n;
    for(int i=0;i<n;i++)
        fin>>p[i].x>>p[i].y;
    fin.close();
    int ras=0;
    sort(p,p+n,comp);
    for(int i=0;i<n;++i)
        for(int j=i+1;j<n;++j)
        {
            double midx,midy;
            midx=(p[i].x+p[j].x)/2;
            midy=(p[i].y+p[j].y)/2;
            double cx=fabs(midx-p[i].x);
            double cy=fabs(midy-p[j].y);
            double x3,x4,y3,y4;
            if(p[j].y>p[i].y)
            {
                x3=midx-cy;
                x4=midx+cy;
                y3=midy+cx;
                y4=midy-cx;
            }
            else
            {
                x3=midx+cy;
                x4=midx-cy;
                y3=midy+cx;
                y4=midy-cx;
            }
            //cout<<i<<' '<<j<<' '<<x3<<' '<<x4<<'\n';
            if(binary_search(i,j,x3,y3) && binary_search(i,j,x4,y4))
                ++ras;

        }
    fout<<ras;
    fout.close();
}

int main()
{
    read();
}





//Interesting Array
/*#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int l[N], r[N], q[N], a[N], st[4 * N];
int sum[N];

void construct(int l,int r,int nod)
{
    if(l==r)
    {
        st[nod]=a[l];
        return;
    }
    if(l>r)
        return;
    int mij=(l+r)/2;
    construct(l,mij,2*nod);
    construct(mij+1,r,2*nod+1);
    st[nod]=st[2*nod] & st[2*nod+1];
}

int query(int nod, int l, int r, int L, int R) {
 	if (l <= L && r >= R) {
 	 	return st[nod];
 	}
 	int mid = (L + R) >> 1;
 	int ans = (1ll << 30) - 1;

 	if(R<l || L>r)
        return ans;

 	return ans&query(2*nod,l,r,L,mid)&query(2*nod+1,l,r,mid+1,R);
}

int main() {
    int n, m;
    cin>>n>>m;
    for(int i = 0; i < m; i++)
        cin>>l[i]>>r[i]>>q[i];

    	for(int bit = 0; bit <= 30; bit++) {
            int mask=(1<<bit);
    		for(int i=0;i<=n;++i)
                sum[i]=0;
    		for(int i = 0; i < m; i++) {
    			if (q[i] & mask) {
    				sum[l[i]]++;
    				sum[r[i]+1]--;
    	 		}
    	 	}
    	 	for(int i = 1; i <= n; i++) {
    	 	 	sum[i] += sum[i - 1];
    	 	 	if (sum[i] > 0) {
    	 	 	 	a[i] |= mask;
    	 	 	}
    	 	}
    }

    construct(1,n,1);

    for(int i = 0; i < m; i++) {
        if (query(1, l[i], r[i], 1, n) != q[i]) {
            cout<<"NO";
            return 0;
        }
    }

    cout<<"YES\n";
    for(int i = 1; i <=n; i++) {
        cout<<a[i]<<' ';
    }
}*/

//Kefa and company
/*#include<bits/stdc++.h>
#define N 1000002
using namespace std;

struct prieten{
    long long m,f;
} v[N];

long long ps[N];

bool cmp(prieten p1,prieten p2)
{
    return p1.m<p2.m;
}

int main()
{
    int n,d;
    cin>>n>>d;
    for(int i=0;i<n;++i)
        cin>>v[i].m>>v[i].f;
    sort(v,v+n,cmp);
    long long fsum=0;
    for(int i=0;i<n;++i)
    {
        fsum+=v[i].f;
        ps[i]=fsum;
    }
    int before=0,after=1;
    int dist=0;
    long long ans=v[0].f,dst;
    while(after<n)
    {
        if(v[after].m-v[before].m<d)
            ans=max(ans,ps[after]-ps[before-1]);
        else{
            dst=v[after].m-v[before].m;
            while(dst>=d)
            {
                ++before;
                dst=dst=v[after].m-v[before].m;
            }
            ans=max(ans,ps[after]-ps[before-1]);
        }
        ++after;
    }
    cout<<ans;
}*/


//mit
/*#include<bits/stdc++.h>
#define N 100005
using namespace std;
int n,v[N];
int st[4*N],lazy[4*N];

void construct(int v[],int l,int r,int nod)
{
    if(l==r)
    {
        st[nod]=v[l];
        return;
    }
    if(l>r)
        return;
    int mij=(l+r)/2;
    construct(v,l,mij,2*nod);
    construct(v,mij+1,r,2*nod+1);
    st[nod]=max(st[2*nod],st[2*nod+1]);
}

int get_max(int l,int r,int nod,int ql,int qr)
{
    if(lazy[nod])
    {
        st[nod]+=lazy[nod];
        if(l!=r){
        lazy[2*nod]+=lazy[nod];
        lazy[2*nod+1]+=lazy[nod];
        }
        lazy[nod]=0;

    }

    if(l>=ql && r<=qr)
        return st[nod];

    if(r<ql || l>qr)
        return 0;

    int mij=(l+r)/2;
    return max(get_max(l,mij,2*nod,ql,qr),get_max(mij+1,r,2*nod+1,ql,qr));

}

void update(int l,int r,int nod,int ql,int qr,int add)
{
    if(lazy[nod])
    {
        st[nod]+=lazy[nod];
        if(l!=r){
        lazy[2*nod]+=lazy[nod];
        lazy[2*nod+1]+=lazy[nod];
        }
        lazy[nod]=0;
    }
    if(r<ql || l>qr)
        return;
    if(l>r)
        return;
    if(l>=ql && r<=qr)
    {
        st[nod]+=add;
        if(l!=r){
        lazy[2*nod]+=add;
        lazy[2*nod+1]+=add;
        }
        return;
    }
    int mij=(l+r)/2;
    update(l,mij,2*nod,ql,qr,add);
    update(mij+1,r,2*nod+1,ql,qr,add);
    st[nod]=max(st[2*nod],st[2*nod+1]);
}

int main()
{
    freopen("mit.in","r",stdin);
    freopen("mit.out","w",stdout);
    int q;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;++i)
        scanf("%d",&v[i]);
    construct(v,1,n,1);
    while(q--)
    {
        int x,a,b,c;
        scanf("%d",&x);
        if(x==1)
        {
            scanf("%d%d",&a,&b);
            printf("%d\n",get_max(1,n,1,a,b));
        }
        else
        {
            scanf("%d%d%d",&a,&b,&c);
            update(1,n,1,a,b,c);
        }
    }
}*/


//Stramosi
/*#include<bits/stdc++.h>
#define N 250010
#define LG 18
using namespace std;
int n,dp[N][LG+1],q;
int main()
{
    ifstream fin("stramosi.in");
    ofstream fout("stramosi.out");
    fin>>n>>q;
    for(int i=1;i<=n;++i)
        fin>>dp[i][0];
    for(int i=1;i<=n;++i)
        for(int j=1;j<=LG;++j)
            dp[i][j]=dp[dp[i][j-1]][j-1];
    while(q--)
    {
        int d,p;
        fin>>d>>p;
        for(int i=LG;i>=0;--i)
            if(p & (1<<i))
                d=dp[d][i];
        fout<<d<<'\n';
    }
    fin.close();
    fout.close();
}*/

//Pikachu
/*#include<bits/stdc++.h>
#define med(k) (k&1 ? k/2 : k/2-1)
using namespace std;

int n,k;
vector<int> a,aj; //ma folosesc de el ca sa aflu costul in timp liniar
long long ans;

int main()
{
    ifstream fin("pikachu.in");
    fin>>n>>k;
    a.reserve(n);
    for(int i=0;i<n;++i)
        fin>>a[i];
    fin.close();
    set<int> s;

    for(int i=0;i<k;++i){
        s.insert(a[i]);
        aj.push_back(a[i]);
    }
    nth_element(aj.begin(),aj.begin()+(med(k)),aj.end());
    int mij=aj[med(k)];
    long long sum=0;
    //cout<<aj[1];
    for(int i=0;i<med(k);++i)
        sum+=abs(aj[i]-mij);
    for(int i=med(k)+1;i<k;++i)
        sum+=abs(aj[i]-mij);
    ans=sum;
    //cout<<sum;
    for(int i=k;i<n;++i)
    {
        set<int>::iterator it=s.find(mij);
        int m=*(--it);
        ++it;
        int M=*(++it);
        int mijb=mij;
        //cout<<sum<<' ';

        s.erase(a[i-k]);
        s.insert(a[i]);

        if (a[i-k]==mij){
			if (a[i]>=m && a[i]<=M) mij=a[i];
            if (a[i]<m) mij=m;
            if(a[i]>M) mij=M;
        }
		if (a[i-k]==m){
            if (a[i]<mij) ;
			else
                if (a[i]>=mij && a[i]<=M) mij=a[i];
				else mij=M;
		}
		if (a[i-k]==M){
			if (a[i]>=m && a[i]<=mij) mij=a[i];
			else
				if (a[i]<m) mij=m;
		}
		if (a[i-k]<m)
			if (a[i]>M) mij=M;
			else if (a[i]>mij) mij=a[i];
		if (a[i-k]>M){
		    if(a[i]>mij);
			if (a[i]<m) mij=m;
			else if (a[i]<mij) mij=a[i];
		}
        sum-=fabs(mijb-a[i-k]);
        sum+=fabs(mij-a[i]);
        if(k%2==0)
            {   //cout<<"45";
                sum+=mijb-mij;
            }
        //pentru k par dif dintre mij si mijb e la fel, iar diferentele aparente dintre restul
        //sunt opuse 2 cate 2
        ans=min(ans,sum);

    }
    ofstream fout("pikachu.out");
    fout<<ans;
    fout.close();
}*/