題目鏈接：點擊查看

題目大意：在一個二維平面上，給出一個初始點 P ，接下來給出 n 個點當做靶子，現在初始節點會射擊每個靶子，我們可以進行的操作是在 x 軸或 y 軸上建造一段連續長度的木板，使得初始點 P 無法射擊到木板后方的靶子，規定木板只能在 x 軸或 y 軸上建造連續的一段，不許拐彎，問最短需要建造多長的木板，才能讓點 P 最多只能射擊到 k 個靶子，如果無解，輸出 -1

題目分析：簡單的幾何問題+貪心，比賽的時候忘記貪心了，結果改來改去還是一直WA，題目給出的點永遠都不會在坐標軸上，那么我們可以先給每個點進行分類：

與點 P 在同一象限的點

與點 P 以 x 軸分隔的點

與點 P 以 y 軸分隔的點

分好類后，首先特判 -1 的情況，就是當我們蓋住 x 軸另一側的所有點或 y 軸另一側的所有點后，還是無法滿足剩余的點小于等于 k，那么此時肯定是輸出 -1，接下來利用直線相交的模板，分別計算出點 P 與 x 軸另一側的每個點與 x 軸的交點，并以此排序，顯然用木板蓋住連續相鄰的點是最優的情況，我們計算一下還需要刪掉多少個點，遍歷一下所有點在維護一下最小值就是答案了，代碼的話可能看起來比較嚇人，其實是為了方便理清思路才把每個變量的名字都寫的那么長的

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=3e5+100;const double eps = 1e-10;int sgn(double x){if(fabs(x) < eps)return 0;if(x < 0)return -1;else return 1; }struct Point{double x,y;Point(){}Point(double _x,double _y){x = _x;y = _y;}void input(){scanf("%lf%lf",&x,&y);}Point operator -(const Point &b)const{return Point(x-b.x,y-b.y);}//叉積double operator ^(const Point &b)const{return x*b.y - y*b.x;}//點積double operator *(const Point &b)const{return x*b.x + y*b.y;} };struct Line{Point s,e;Line(){}Line(Point _s,Point _e){s = _s;e = _e;}//`求兩直線的交點`//`要保證兩直線不平行或重合`Point crosspoint(Line v){double a1 = (v.e-v.s)^(s-v.s);double a2 = (v.e-v.s)^(e-v.s);return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1));} };vector<Point>_1,_2,_3;//1:同一象限內 2:y軸另一側 3:x軸另一側 int main() { //#ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); //#endif // ios::sync_with_stdio(false);Point point,temp;point.input();int n,k;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){temp.input();if((sgn(temp.x*point.x)>0&&sgn(temp.y*point.y)>0))//位于同一象限 _1.push_back(temp);if((sgn(temp.x*point.x)<0))//位于y軸另一側 _2.push_back(temp);if((sgn(temp.y*point.y)<0))//位于x軸另一側 _3.push_back(temp);}if(n-max(_2.size(),_3.size())>k)puts("-1");else{vector<double>point_y,point_x;int len=(n-_1.size())-(k-_1.size());//還需要刪掉這么多點才行 double ans=1e10;for(int i=0;i<_2.size();i++)//計算跨y軸的木板長度(在y軸上){Point temp=Line(point,_2[i]).crosspoint(Line(Point(0,0),Point(0,1)));point_y.push_back(temp.y);} sort(point_y.begin(),point_y.end());for(int i=0;i+len-1<point_y.size();i++)ans=min(ans,point_y[i+len-1]-point_y[i]);for(int i=0;i<_3.size();i++)//計算跨x軸的木板長度(在x軸上){Point temp=Line(point,_3[i]).crosspoint(Line(Point(0,0),Point(1,0)));point_x.push_back(temp.x);}sort(point_x.begin(),point_x.end());for(int i=0;i+len-1<point_x.size();i++)ans=min(ans,point_x[i+len-1]-point_x[i]);printf("%f\n",ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的牛客 - umi和弓道(几何+贪心)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。