WorldFinal 11
Trash Removal
题意
给你一个多边形，问这个多边形至少需要多宽的长度，才能把这个多边形放进去。
数据范围100
题解
数据范围只有100，暴力枚举两点，然后算最小距离就好了
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
const double eps = 1e-6;
int cnt=0;
struct node{
double x,y;
}p[105];
double sqr(double x)
{
return x*x;
}
double dis(node a,node b)
{
return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}
node operator - (node a,node b)
{
node ret;
ret.x=a.x-b.x;
ret.y=a.y-b.y;
return ret;
}
double operator * (node a,node b)
{
return a.x*b.x+a.y*b.y;
}
double operator ^ (node a,node b)
{
return a.x*b.y-b.x*a.y;
}
double distoline(node a,node b,node c)//a到bc的有向距离
{
double l1=fabs((a-b)*(c-b))/dis(b,c);
return sqrt(sqr(dis(a,b))-l1*l1);
}
int main()
{
int n;
while(cin>>n)
{
if(n==0)break;
for(int i=1;i<=n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
double ans = 1e9;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)continue;
int flag = 0;
for(int k=1;k<=n;k++){
if(k==i||k==j)continue;
if(((p[k]-p[i])^(p[j]-p[i]))<0.000){
flag=1;
break;
}
}
if(flag)continue;
double d = 0;
for(int k=1;k<=n;k++){
if(k==i||k==j)continue;
d=max(d,distoline(p[k],p[i],p[j]));
}
ans=min(ans,d);
}
}
int Ans = (int)(ans*100+0.99999999999);
printf("Case %d: %.2f
",++cnt,Ans/(100.0));
}
}
Mummy Madness
题意
二维平面有n<100000个僵尸，还有你。
你一开始在(0,0)位置，僵尸在(x,y),(x,y<=1e5)位置。
僵尸会抓你，你负责逃跑。
这是一个8连通的二维平面，僵尸和你，每一秒都跑一个格子，问你最迟什么时候被抓住，如果不能，输出never。
题解
显然二分，二分答案之后，我能够走的位置是一个正方形，僵尸也是正方形。
通过扫描线维护，看看我所走的正方形，是否完全被僵尸覆盖就好了。
（hdu给的五秒把我卡死了。。。UVA给的20秒）
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6+7;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct node
{
int l,r;
int lazy,Min;
void update(int x)
{
lazy+=x;
Min+=x;
}
}tree[maxn*4];
void build(int x,int l,int r)
{
tree[x].l=l,tree[x].r=r;
tree[x].Min=tree[x].lazy=0;
if(l==r)return;
int mid=(l+r)/2;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
}
void push_down(int x)
{
int lazyval=tree[x].lazy;
if(lazyval){
tree[x<<1].update(lazyval);
tree[x<<1|1].update(lazyval);
}
tree[x].lazy=0;
}
void push_up(int x)
{
tree[x].Min=min(tree[x<<1].Min,tree[x<<1|1].Min);
}
void update(int x,int l,int r,int val)
{
if(r<l)return;
int L=tree[x].l,R=tree[x].r;
if(l<=L&&R<=r)
tree[x].update(val);
else{
push_down(x);
int mid=(L+R)/2;
if(mid>=l)update(x<<1,l,r,val);
if(mid<r)update(x<<1|1,l,r,val);
push_up(x);
}
}
int query(int x,int l,int r)
{
if(r<l)return 0;
int L=tree[x].l,R=tree[x].r;
if(l<=L&&R<=r)return tree[x].Min;
push_down(x);
int res=1e9;
int mid=(L+R)/2;
if(mid>=l)res=min(res,query(x<<1,l,r));
if(mid<r)res=min(res,query(x<<1|1,l,r));
return res;
}
int n;
int x[maxn],y[maxn];
struct Li
{
int a[maxn];
int tot=0;
void clear(){
tot=0;
}
void push_back(int x){
a[++tot]=x;
}
void Sort(){
sort(a+1,a+1+tot);
int j=1;
for(int i=2;i<=tot;i++)
if(a[i]!=a[i-1])
a[++j]=a[i];
tot=j;
}
int getid(int x)
{
int l=1,r=tot,ans=1;
while(l<=r)
{
int mid=(l+r)/2;
if(a[mid]<=x)l=mid+1,ans=mid;
else r=mid-1;
}
return ans;
}
int size()
{
return tot;
}
}V;
vector<int>q;
vector<pair<pair<int,int>,pair<int,int> > >ask;
bool check(int dis)
{
V.clear();q.clear();
V.push_back(-dis),V.push_back(dis+1);ask.clear();
for(int i=1;i<=n;i++)
V.push_back(y[i]-dis);
for(int i=1;i<=n;i++)
V.push_back(y[i]+dis+1);
V.Sort();
for(int i=1;i<=n;i++)
{
ask.push_back(make_pair(make_pair(x[i]-dis,1),make_pair(y[i]-dis,y[i]+dis+1)));
ask.push_back(make_pair(make_pair(x[i]+dis+1,-1),make_pair(y[i]-dis,y[i]+dis+1)));
}
for(int i=1;i<=n;i++){
if(x[i]-dis>=-dis&&x[i]-dis<=dis)q.push_back(x[i]-dis);
if(x[i]+dis+1>=-dis&&x[i]+dis+1<=dis)q.push_back(x[i]+dis+1);
}
q.push_back(-dis);
sort(ask.begin(),ask.end());
sort(q.begin(),q.end());
q.erase(unique(q.begin(),q.end()),q.end());
build(1,1,V.size()+5);
int now=0;
for(int i=0;i<q.size();i++){
while(now<ask.size()&&ask[now].first.first<=q[i]){
int l=V.getid(ask[now].second.first);
int r=V.getid(ask[now].second.second)-1;
update(1,l,r,ask[now].first.second);
now++;
}
if(q[i]<=dis&&q[i]>=-dis)
if(query(1,V.getid(-dis),V.getid(dis+1)-1)==0)
return true;
}
return false;
}
int main()
{
int cas=0;
while(scanf("%d",&n)!=EOF)
{
if(n==-1)break;
for(int i=1;i<=n;i++)
x[i]=read(),y[i]=read();
int l=1,r=1e6+7,ans=1e6+7;
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid))l=mid+1;
else r=mid-1,ans=mid;
}
if(ans>1e6){
printf("Case %d: never
",++cas);
}else{
printf("Case %d: %d
",++cas,ans);
}
}
}