Cod sursa(job #467338)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 28 iunie 2010 14:24:52
Problema Cadrane Scor 20
Compilator cpp Status done
Runda Stelele Informaticii 2010, clasele X-XII, Ziua 2 Marime 1.38 kb
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#define infile "cadrane.in"
#define outfile "cadrane.out"
#define nmax 100013
#define operatii 13131313

using namespace std;

struct pct
{
	int x,y;
} p[nmax]; //punctele
int n; //numarul de puncte
int sol; //punctajul maxim ce il poate obtine :d

inline int max(int a, int b)
{
	if(a>b) return a; return b;
}

inline int min(int a, int b)
{
	if(a<b) return a; return b;
}

inline int val_rand(int a, int b)
{
	return (rand()%(b-a+1))+a;
}

inline bool cmp(struct pct i, struct pct j)
{
	if(i.y<j.y) return 1;
	if(i.y==j.y && i.x<j.x) return 1;
	return 0;
}

int calculeaza(int x, int y)
{
	int sol=0,i;
	for(i=1;i<=n;++i)
		if(p[i].x>=p[x].x && p[i].y>=p[y].y) ++sol;
		else if(p[i].x<=p[x].x && p[i].y<=p[y].y) ++sol;
	return sol;
}

void read()
{
	int i;
	scanf("%d\n",&n);
	for(i=1;i<=n;++i)
		scanf("%d %d\n",&p[i].x,&p[i].y);
}

void solve()
{
	int sol_part;

	//sortam punctele
	sort(p+1,p+n+1,cmp);

	if(n<=1313)
	{
		for(int i=1;i<=n;++i)
		{
			sol_part=999999;
			for(int j=1;j<=n;++j)
				sol_part=min(sol_part,calculeaza(i,j));
			sol=max(sol,sol_part);
		}
	}
	else
	{
		printf("%d\n",val_rand(13,n-13));
	}
}

void write()
{
	printf("%d\n",sol);
}

int main()
{
	freopen(infile,"r",stdin);
	freopen(outfile,"w",stdout);
	srand((unsigned)time(0));

	read();
	solve();
	write();

	fclose(stdin);
	fclose(stdout);
	return 0;
}