CF1486B Eastern Exhibition

CF1486B Eastern Exhibition

题意：

二维平面上有 n 个点，要找一个点，使得所有点到它的曼哈顿距离（ x 和 y 的坐标差距之和）之和最小。请问有几个满足该要求的点？

题解：

我们先考虑一维的情况，在一个数轴上，存在n个点，现在要找一个为位置pos，使得pos到其他点的距离和最小？
很显然，如果n为奇数，我们就选最中间的点为pos，如果n为偶数，那就是最中间两个数的中位数
现在问题变成二维的了，现在要找点(x,y)到其他点的距离和最小，x和y我们是可以分开考虑的，因为x只与横坐标有关，y只与纵坐标有关，那问题就变成两个一维的情况，然后两个所围成的面积，里面的点都是满足要求的

代码：

#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; void read(){}; template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar) {x= 0;char c= getchar();bool flag= 0;while (c < '0' || c > '9')flag|= (c == '-'), c= getchar();while (c >= '0' && c <= '9')x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();if (flag)x= -x;read(Ar...); } template <typename T> inline void write(T x) {if (x < 0) {x= ~(x - 1);putchar('-');}if (x > 9)write(x / 10);putchar(x % 10 + '0'); } void rd_test() { #ifdef ONLINE_JUDGE #elsestartTime = clock ();freopen("data.in", "r", stdin); #endif } void Time_test() { #ifdef ONLINE_JUDGE #elseendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } const int maxn=1e3+9; ll x[maxn],y[maxn]; int main() {//rd_test();int t;read(t);while(t--){int n;cin>>n;for(int i=1;i<=n;i++){cin>>x[i]>>y[i];}if(n&1==1){printf("1\n");continue;}sort(x+1,x+1+n);sort(y+1,y+1+n);ll ans1=x[n/2+1]-x[n/2]+1;ll ans2=y[n/2+1]-y[n/2]+1;cout<<ans1*ans2<<endl;}return 0; //Time_test(); }

总结

以上是生活随笔为你收集整理的CF1486B Eastern Exhibition的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。