MikawithCherryCake

Mika wants to make some cherry cakes to eat.

The forest Mika lives can be considered as a two-dimensional Cartesian coordinate. Mika's home is located on $\text (0,0)$ .

In the forest, the speed of Mika and merchant is same. If you want to go from $\text (x,y)$ to $\text (x',y')$ , you will cost $\text|x-x'|+|y-y'|$ seconds, which is the Manhattan distance between them.

If one person if on $\text (x,y)$ , when he
go up for $\mathit t$ seconds, he will be at $\text (x,y+t)$ ,
go down for $\mathit t$ seconds, he will be at $\text (x,y-t)$ ,
go right for $\mathit t$ seconds, he will be at $\text (x+t,y)$ ,
go left for $\mathit t$ seconds, he will be at $\text (x-t,y)$ .
Notice: $\mathit t$ may not be an integer.

Now Mika knows that there will be $\mathit n$ merchants travel through this forest. The $\mathit i^{th}$ merchant will be at $\text (x_{i},y_{i})(x_i\geq 1, y_i \geq 1)$ at time $\text 0$ and the diraction of each merchant will be given.

Mika will be at his home at time $\text 0$ , when he and a merchant are at the same point, he can buy a basket of cherry, and return to the home to drop the basket, then he goes to find the second merchant and so on. You can consider the time Mika spends on buying cherries and dropping the basket at home is $\text 0$ .

Mika is a fairy, so he can't hold two or more baskets of cherry, so he can only buy one basket of cherry and return home to drop the basket.

Now Mika wants to know the maximum baskets of cherry he can buy?

The first line is an integer $\mathit n$ , repersenting the number of merchant.
The next $\mathit n$ lines are Three integers $x_{i},y_{i},dir_{i}$ ,representing the position of the $i^{th}$ merchant and the direction the $i^{th}$ merchant travels.
$1\leq n \leq 5000$
$1\leq x_{i},y_{i} \leq 10^{8}$
$dir_{i}\in {\lbrace 1,2,3,4 \rbrace}$
If $dir_{i}=1$ , the merchant is moving up.
If $dir_{i}=2$ , the merchant is moving down.
If $dir_{i}=3$ , the merchant is moving right.
If $dir_{i}=4$ , the merchant is moving left.

#include<bits/stdc++.h> using namespace std; vector<pair<int,int> > v; int main(){ int t; cin>>t; while(t--){ int a,b,c; cin>>a>>b>>c; if(c==1||c==3) continue; if(c==2) v.push_back(make_pair(a+b, a)); if(c==4) v.push_back(make_pair(a+b, b)); } int ans = 0; int now = 0; sort(v.begin(),v.end()); for(int i=0;i<v.size();i++){ if(v[i].second*2+now<=v[i].first){ ans++; now=v[i].first; } } cout<<ans<<endl; return 0; }

详情