[USACO 2012 Mar S]Flowerpot

Farmer John has been having trouble making his plants grow, and needs your help to water them properly. You are given the locations of N raindrops (1 <= N <= 100,000) in the 2D plane, where y represents vertical height of the drop, and x represents its location over a 1D number line:

Each drop falls downward (towards the x axis) at a rate of 1 unit per second. You would like to place Farmer John's flowerpot of width W somewhere along the x axis so that the difference in time between the first raindrop to hit the flowerpot and the last raindrop to hit the flowerpot is at least some amount D (so that the flowers in the pot receive plenty of water). A drop of water that lands just on the edge of the flowerpot counts as hitting the flowerpot.

Given the value of D and the locations of the N raindrops, please compute the minimum possible value of W.

#include <bits/stdc++.h> using namespace std; #define pii pair<int,int> #define x first #define y second const int M=1e5+5; pii a[M],st[M]; int main() { int h=1,t=0,ans=1e9; int n,m; cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y; sort(a+1,a+1+n); for(int i=1;i<=n;i++) { while(h<=t&&st[t].y>=a[i].y)t--; st[++t]=a[i]; while(st[t].y-st[h].y>=m)ans=min(ans,st[t].x-st[h++].x); } printf("%d",ans==1e9?-1:ans); return 0; }

详情