Pagini recente » Cod sursa (job #2343868) | Cod sursa (job #2960390) | Cod sursa (job #2262128) | Cod sursa (job #49686) | Cod sursa (job #2557896)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("pachete.in");
ofstream fout("pachete.out");
int n, i, st, dr, mid, x, y, xSediu, ySediu, v[50010], k, aux;
vector < pair<int, int> > cadran1;
vector < pair<int, int> > cadran2;
vector < pair<int, int> > cadran3;
vector < pair<int, int> > cadran4;
int solutie(vector < pair<int, int> > cadran){
if(cadran.size()==0){
return 0;
}
sort(cadran.begin(), cadran.end());
k=1;
v[1]=cadran[0].second;
for(int i=1; i<cadran.size(); i++){
aux=cadran[i].second;
st=1;
dr=k;
while(st<=dr){
mid=(st+dr)/2;
if(v[mid]>aux){
st=mid+1;
}else{
dr=mid-1;
}
}
if(st==k+1){
k++;
}
v[k]=aux;
}
return k;
}
/// normalizez punctele, consider sediul ca originea sistemului
/// incadrez punctele in cadrane si le rezolv separat
int main(){
fin>>n;
fin>>xSediu>>ySediu;
for(i=1; i<=n; i++){
fin>>x>>y;
x-=xSediu;
y-=ySediu;
if(x>=0){
if(y>=0){
cadran1.push_back({x, y});
}else{
cadran4.push_back({x, -y});
}
}else{
if(y>=0){
cadran2.push_back({-x, y});
}else{
cadran3.push_back({-x, -y});
}
}
}
fout<<solutie(cadran1)+solutie(cadran2)+solutie(cadran3)+solutie(cadran4);
}