首页 > 代码库 > A - Superset CodeForces - 97B（人生第一个分治法，感觉，像二分啊。。）
A - Superset CodeForces - 97B（人生第一个分治法，感觉，像二分啊。。）
/*
分治法，第一次做不是很懂，借鉴了神犇代码，但实操之后感觉像二分，，可能做得少了或者就是。。。。
*/
题目大意：
一个集合里有若干点，要求你添加某些点后保证这个集合里的任意两点满足以下三个条件中至少一个：
1.在一个水平线上 2.在一个竖直线上 3.两点组成的矩形之间有点.
解题思路：
神犇所讲，将点排序，在中间点处建一条竖直线，令其余点在其上投影，二分。
ps：不是很明白错误是什么，，结构体里重载＜运算符可以，但是写个cmp函数就报错，不是很懂，贴上错误代码，如果神犇们知道什么错误，请评论告知，多谢；
错误代码
#include<iostream> #include <vector> #include <algorithm> #include <queue> #include <stack> #include <set> #include <cstdio> #include <iterator> #include <sstream> #include <cmath> #include <deque> using namespace std; struct node { int x; int y; // bool operator <(const node b)const // { // if(x==b.x) return y<b.y; // else return x<b.x; // } }; int n; node p1[10050]; set<node > p; bool cmp(const node a,const node b) { return a.x<b.x; } void dfs(int l,int h) { if (l==h) return ; int mid; mid=(l+h)/2; for (int i=l; i<=h; i++) { node c; c.x=p1[mid].x; c.y=p1[i].y; p.insert(c); } dfs(l,mid); dfs(mid+1,h); } int main() { cin>>n; for (int i=0; i<n; i++) { cin>>p1[i].x>>p1[i].y; p.insert(p1[i]); } sort(p1,p1+n,cmp); dfs(0,n-1); cout<<p.size()<<endl; set<node >::iterator it; for (it=p.begin(); it!=p.end(); it++) { cout<<(*it).x<<" "<<(*it).y<<endl; } }
AC代码：
#include<iostream> #include <vector> #include <algorithm> #include <queue> #include <stack> #include <set> #include <cstdio> #include <iterator> #include <sstream> #include <cmath> #include <deque> using namespace std; struct node { int x; int y; bool operator <(const node b)const { if(x==b.x) return y<b.y; else return x<b.x; } }; int n; node p1[10050]; set<node > p; bool cmp(const node a,const node b) { return a.x<b.x; } void dfs(int l,int h) { if (l==h) return ; int mid; mid=(l+h)/2; for (int i=l; i<=h; i++) { node c; c.x=p1[mid].x; c.y=p1[i].y; p.insert(c); } dfs(l,mid); dfs(mid+1,h); } int main() { cin>>n; for (int i=0; i<n; i++) { cin>>p1[i].x>>p1[i].y; p.insert(p1[i]); } sort(p1,p1+n); dfs(0,n-1); cout<<p.size()<<endl; set<node >::iterator it; for (it=p.begin(); it!=p.end(); it++) { cout<<(*it).x<<" "<<(*it).y<<endl; } }
A - Superset CodeForces - 97B（人生第一个分治法，感觉，像二分啊。。）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。