就是给出非常多点,要求分成两个集合,在同一个集合里的点要求随意两个之间的距离都大于5。
求一个集合。它的点数目是全部可能答案中最少的。
直接从随意一个点爆搜,把它范围内的点都丢到跟它不一样的集合里。不断这样搞即可了。
由于可能有非常多相离的远,把每次搜索得到的那个最小的数目加起来就可以。
因为全部点都格点上,所以仅仅须要枚举一个点可以包括的点是否在数据中存在就可以。
当然也能够用一棵树直接去找。这我并不会。。
时间复杂度是81nlogn
湖大的OJ机器太老。。
。还要开栈。
。
。UVA LIVE随便交就过了。
#include<map>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<climits>
#include<list>
#include<iomanip>
#include<stack>
#include<set>
using namespace std;
struct Point
{
int x,y;
Point(){}
Point(int x,int y)
{
this->x=x;
this->y=y;
}
bool operator <(Point one)const
{
if(x!=one.x)
return x<one.x;
return y<one.y;
}
};
vector<Point>bx;
int dis2(Point one,Point two)
{
return (one.x-two.x)*(one.x-two.x)+(one.y-two.y)*(one.y-two.y);
}
void create()
{
for(int i=-5;i<=5;i++)
for(int j=-5;j<=5;j++)
if(dis2(Point(i,j),Point(0,0))<=25)
bx.push_back(Point(i,j));
}
map<Point,int>mp;
Point cnt;
void dfs(Point v)
{
int n=bx.size(),no=mp[v];
map<Point,int>::iterator it;
for(int i=0;i<n;i++)
{
Point t=Point(v.x+bx[i].x,v.y+bx[i].y);
it=mp.find(t);
if(it!=mp.end()&&it->second==0)
{
if(no==1)
{
it->second=2;
cnt.y++;
}
else
{
it->second=1;
cnt.x++;
}
dfs(t);
}
}
}
int main()
{
//int size = 256 << 20; // 256MB
// char *p = (char*) malloc (size) + size;
// __asm__ ("movl %0, %%esp\n" :: "r" (p) );
create();
int n;
while(scanf("%d",&n)!=EOF)
{
while(n--)
{
Point t;
scanf("%d%d",&t.x,&t.y);
mp[t]=0;
}
map<Point,int>::iterator it;
int ans=0;
for(it=mp.begin();it!=mp.end();it++)
{
if(it->second==0)
{
it->second=1;
cnt.x=1;
cnt.y=0;
dfs(it->first);
if(cnt.x>cnt.y)
swap(cnt.x,cnt.y);
ans+=cnt.x;
}
}
cout<<ans<<endl;
}
return 0;
}
Time Limit: 15000ms, Special Time Limit:37500ms, Memory Limit:65536KB |
Total submit users: 9, Accepted users: 6 |
Problem 13307 : No special judgement |
Problem description |
The Andromeda galaxy is expected to collide with our Milky Way in about 3.8 billion years. The collision will probably be a merging of the two galaxies, with no two stars actually colliding. That is because the distance between stars in both galaxies is |
Input |
The first line contains an integer N (1 ≤ N ≤ 5×10^4) representing the number of points in the set. Each of the next N lines describes a different point with two integers X and Y (1 ≤ X,Y ≤ 5 × 10^5), indicating its coordinates, in light years. There are |
Output |
Output a line with an integer representing the minimum number of points a subset may have in a good separation. |
Sample Input |
Sample input 1 |
Sample Output |
Sample output 1 |
Problem Source |
ICPC Latin American Regional ?
2014 |