题意：给定n个点，对于每次消失一个点，问剩下的点中的最短距离是多少，然后所有最短距离的和。 分析：1、模版题，然而没模版的我码了半天。 2、（1）只要不删掉与最短距离相关的两个点，那么最短距离不变。 （2）若与最短距离的点相关，删掉点后，重新算一遍。 /************************************************ Author :DarkTong Created Time :2016/7/18 14:01:14 File Name :d.cpp *************************************************/ #include #include #include #include #include #include #include <set> #include #include <string> #include #include #include #define INF 0x3fffffffffffffff #define esp 1e-9 typedef long long LL; using namespace std; const int maxn = 100000 + 100; typedef LL Int; struct Node { Int x, y; int id; Node(Int x=0, Int y=0, int i=-1):x(x), y(y), id(i){} bool operator==(Node &a){return x==a.x&&y==a.y;} }; vector poi; //求两点的距离 Int dis(Node &a, Node &b){ return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y); } //各种按不同优先级排序的排序函数 int cmpx(const Node &a, const Node &b){ return a.x==b.x ? a.yb.x;} int cmpy(const Node &a, const Node &b){ return a.y==b.y ? a.xb.y;} int cmpi(const Node &a, const Node &b){ return a.id<b.id;} int ans1, ans2; int n, xxx; LL ansd; /*****************************************/ /*合并两个集合的点，找出最短距离的两个点 */ /*****************************************/ void Merger(int L, int R, int m, Int &ans) { int tl, tr, t; //选出右边离中心线距离<=max(dl, dr)的点 tl=tr=m; while(tr; sort(poi.begin()+tl, poi.begin()+tr, cmpy); int ta1, ta2; //枚举左边的点，选出与其最近的点。 for(int i=L;ii) { if(poi[i].id==xxx) continue; int l, r; r = upper_bound(poi.begin()+tl, poi.begin()+tr, poi[i], cmpy) - poi.begin(); l = max(tl, r-3); r = min(tr, r+3); for(int j=l; jj) { if(poi[j].id==xxx) continue; if(dis(poi[j], poi[i]) < ans) { ans = dis(poi[j], poi[i]); ta1=poi[i].id; ta2=poi[j].id; } } } //为了得到最近两点的id值 if(ans ta2;} //恢复 sort(poi.begin()+tl, poi.begin()+tr, cmpx); } Int MergerSolve(int L, int R) { int m; Int dl, dr; //边界条件 if(R-L<=3) { int ta1, ta2; Int ans=INF; for(int i=L;ii) { if(poi[i].id==xxx) continue; for(int j=i+1;jj) { if(poi[j].id==xxx) continue; if(dis(poi[i], poi[j])poi[j].id;} } } //用于记录最短距离的那两个点的坐标 if(ans ta2;} return ans; } m = (L+R)>>1; dl=MergerSolve(L, m); dr=MergerSolve(m, R); Int ans = min(dl, dr); //合并操作 Merger(L, R, m, ans); return ans; } int main() { int ca; scanf("%d", &ca); while(ca--) { scanf("%d", &n); int x, y; for(int i=0;ii) { scanf("%d%d", &x, &y); poi.push_back(Node(x, y, i)); } sort(poi.begin(), poi.end(), cmpx); xxx = -1; ansd = INF; LL ttans = MergerSolve(0, n)*(n-2); int ta1 = ans1, ta2 = ans2; xxx = ta1; ansd=INF; ttans += MergerSolve(0, n); xxx = ta2; ansd=INF; ttans += MergerSolve(0, n); cout<endl; poi.clear(); } return 0; }
题意：给定n个点，对于每次消失一个点，问剩下的点中的最短距离是多少，然后所有最短距离的和。
分析：1、模版题，然而没模版的我码了半天。
2、（1）只要不删掉与最短距离相关的两个点，那么最短距离不变。
（2）若与最短距离的点相关，删掉点后，重新算一遍。
/************************************************ Author :DarkTong Created Time :2016/7/18 14:01:14 File Name :d.cpp *************************************************/ #include #include #include #include #include #include #include <set> #include #include <string> #include #include #include #define INF 0x3fffffffffffffff #define esp 1e-9 typedef long long LL; using namespace std; const int maxn = 100000 + 100; typedef LL Int; struct Node { Int x, y; int id; Node(Int x=0, Int y=0, int i=-1):x(x), y(y), id(i){} bool operator==(Node &a){return x==a.x&&y==a.y;} }; vector poi; //求两点的距离 Int dis(Node &a, Node &b){ return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y); } //各种按不同优先级排序的排序函数 int cmpx(const Node &a, const Node &b){ return a.x==b.x ? a.yb.x;} int cmpy(const Node &a, const Node &b){ return a.y==b.y ? a.xb.y;} int cmpi(const Node &a, const Node &b){ return a.id<b.id;} int ans1, ans2; int n, xxx; LL ansd; /*****************************************/ /*合并两个集合的点，找出最短距离的两个点 */ /*****************************************/ void Merger(int L, int R, int m, Int &ans) { int tl, tr, t; //选出右边离中心线距离<=max(dl, dr)的点 tl=tr=m; while(tr; sort(poi.begin()+tl, poi.begin()+tr, cmpy); int ta1, ta2; //枚举左边的点，选出与其最近的点。 for(int i=L;ii) { if(poi[i].id==xxx) continue; int l, r; r = upper_bound(poi.begin()+tl, poi.begin()+tr, poi[i], cmpy) - poi.begin(); l = max(tl, r-3); r = min(tr, r+3); for(int j=l; jj) { if(poi[j].id==xxx) continue; if(dis(poi[j], poi[i]) < ans) { ans = dis(poi[j], poi[i]); ta1=poi[i].id; ta2=poi[j].id; } } } //为了得到最近两点的id值 if(ans ta2;} //恢复 sort(poi.begin()+tl, poi.begin()+tr, cmpx); } Int MergerSolve(int L, int R) { int m; Int dl, dr; //边界条件 if(R-L<=3) { int ta1, ta2; Int ans=INF; for(int i=L;ii) { if(poi[i].id==xxx) continue; for(int j=i+1;jj) { if(poi[j].id==xxx) continue; if(dis(poi[i], poi[j])poi[j].id;} } } //用于记录最短距离的那两个点的坐标 if(ans ta2;} return ans; } m = (L+R)>>1; dl=MergerSolve(L, m); dr=MergerSolve(m, R); Int ans = min(dl, dr); //合并操作 Merger(L, R, m, ans); return ans; } int main() { int ca; scanf("%d", &ca); while(ca--) { scanf("%d", &n); int x, y; for(int i=0;ii) { scanf("%d%d", &x, &y); poi.push_back(Node(x, y, i)); } sort(poi.begin(), poi.end(), cmpx); xxx = -1; ansd = INF; LL ttans = MergerSolve(0, n)*(n-2); int ta1 = ans1, ta2 = ans2; xxx = ta1; ansd=INF; ttans += MergerSolve(0, n); xxx = ta2; ansd=INF; ttans += MergerSolve(0, n); cout<endl; poi.clear(); } return 0; }
BestCoder 2nd Anniversary 1004&Hdu 5721 Palace
![[c++基础]STL](https://img.php1.cn/3c972/1edc8/c5a/a04ecc977fd8ed28.jpeg)
![Spark中使用map或flatMap将DataSet[A]转换为DataSet[B]时Schema变为Binary的问题及解决方案](https://img6.php1.cn/3cdc5/9b0d/243/f27d40b3b7e4b51b.png)
京公网安备 11010802041100号