Cod sursa(job #830406)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 6 decembrie 2012 20:21:45
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <fstream>
#include <algorithm>
#define dim 50002
#include <set>
using namespace std;
 
ifstream f("pachete.in");
ofstream g("pachete.out");

int n,i,x,y,a,b;
set<int>Q;
pair <int, int> cadran[4][dim];

int num[4];
 
int drum(int k){
	int numsub=0;
	
    sort(cadran[k]+1,cadran[k]+num[k]+1);
    
 
  
    set<int>::iterator it;
 
    for (int i=1;i<=num[k];i++) {
        it=Q.lower_bound(cadran[k][i].second);
		
        if (it==Q.begin()) {
            numsub++;//incrementam nr subsiruri
        } 
		else{//stergem ultimul pct din lista
            --it;
            Q.erase(it);
        }
		//inseram punctul curent in lista 
        Q.insert(cadran[k][i].second);
    }
	
    return numsub;
}
 
int main(){
	f>>n;
	f>>a>>b;
    for (i=1;i<=n;i++) {
        f>>x>>y;
		
        x-=a;
		y-=b;// scadam coordonatele sediului firmei
		
        if (x>0&&y>0){//cadranul 1
			num[0]++;
			cadran[0][num[0]].first=x;
			cadran[0][num[0]].second=y;
			
		}
        if (x<0&&y>0){//cadranul 2
			num[1]++;
			cadran[1][num[1]].first=-x;
			cadran[1][num[1]].second=y;
		}
        if (x<0&&y<0){//cadranul 3
			num[2]++;
			cadran[2][num[2]].first=-x;
			cadran[2][num[2]].second=-y;
		}
        if (x>0&&y<0){//cadranul 4
			
			num[3]++;
			cadran[3][num[3]].first=x;
			cadran[3][num[3]].second=-y;
		}
    }
	g<<drum(0)+drum(1)+drum(2)+drum(3);
    return 0;
}