Cod sursa(job #1275279)

Utilizator catalincraciunCraciun Catalin catalincraciun Data 24 noiembrie 2014 22:50:32
Problema Pachete Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
/// Craciun Catalin
///  Pachete
#include <iostream>
#include <fstream>
#include <algorithm>

#define NMax 50005

struct point {
	
	int x;
	int y;
	point() {
		x = 0;
		y = 0;
	}
	point(int a, int b) {
		x = a, y = b;
	};
};

using namespace std;

ifstream f("pachete.in");
ofstream g("pachete.out");

int n, x, y;
point A[5][NMax];
int sz[5];
int v[NMax];

bool compare(const point &A, const point &B) {
	if (A.x == B.x) return A.y < B.y;
	return A.x < B.x;
}
inline int modul (int a) { if ( a > 0 ) return a; return -a; };

int main() {
	
	f>>n;
	f>>x>>y;
	for (int i=1;i<=n;i++) {
		int xp, yp;
		f>>xp>>yp;
		xp -= x; yp -= y;
		if (xp >= 0 && yp >= 0) {
			/// Cadran 1
			sz[1]++;
			A[1][sz[1]] = point(modul(xp), modul(yp));
		} else if (xp >= 0 && yp < 0) {
			/// Cadran 4
			sz[4]++;
			A[4][sz[4]] = point(modul(xp), modul(yp));
		} else if (xp < 0 && yp >= 0) {
			/// Cadran 2
			sz[2]++;
			A[2][sz[2]] = point(modul(xp), modul(yp));
		} else if (xp < 0 && yp < 0) {
			/// Cadran 3
			sz[3]++;
			A[3][sz[3]] = point(modul(xp), modul(yp));
		}
	}
	
	for (int i=1;i<=4;i++)
		sort(A[i]+1, A[i]+1+sz[i], compare);
		
	int sol = 0;
	for (int i=1;i<=4;i++) {
		if (!sz[i]) continue;
		int k = 1;
		v[k] = 1;
		for (int j=2;j<=sz[i];j++) {
			if (A[i][j].y < A[i][v[k]].y) {
				v[++k] = i;
				continue;
			}
			
			int st=1, dr=k;
			while (st <= dr) {
				int mij = (st+dr)>>1;
				if (A[i][j].y < A[i][v[mij]].y) {
					st = mij + 1;
				} else {
					dr = mij - 1;
				}
			}
			
			v[st] = j;
		}
		
		sol+=k;
	}

	g<<sol<<'\n';
	
	f.close(); g.close();
	return 0;
}