注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3199][Sdoi2013]escape  

2015-03-26 19:21:52|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3199: [Sdoi2013]escape

Time Limit: 20 Sec  Memory Limit: 256 MB
Submit: 205  Solved: 94
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

2 4 10 10 5 5 5 6 3 5 7 5 5 3 17 14 12 7 6 7 11 6 9 7 7 1 10 2 20 1 6 2 6 1 1 2 2 5 1 5 2 13 1 12 2 12 7 13 7 12 11 13 11

Sample Output

1 2

HINT

Solution

开始想V图,但是敲完之后发现只有20分。。。(纯属娱乐)
是这样的,如果有四点共圆,就只能连一个四边形,不能连对角线
还有它外面有大框框,这样会改变V图的构型

其实只要暴力求半平面交就好了
uojLink
求完以后跑最短路就好了

Code

V图

/**************************************************************
Problem: 3199
User: wjy1998
Language: C++
Result: Wrong_Answer
****************************************************************/

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 1000
typedef double ld;
#define sqr(x) ((x)*(x))
int aa;char ch;int F(){
while(ch=getchar(),ch<'0'||ch>'9');aa=ch-'0';
while(ch=getchar(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
struct P{ld x,y;}a[N],o,lim,cc;//|->dot &->cross
#define PP const P&
#define gp() (P){F(),F()}
bool operator<(PP a,PP b){return a.x<b.x||a.x==b.x&&a.y<b.y;}
P operator-(PP a,PP b){return (P){a.x-b.x,a.y-b.y};}
ld operator|(PP a,PP b){return a.x*b.x+a.y*b.y;}
ld operator&(PP a,PP b){return a.x*b.y-a.y*b.x;}
ld dis2(PP a){return sqr(a.x)+sqr(a.y);}
ld check(PP a,PP b,PP c){return (b-a)&(c-a);}
bool cross(PP a,PP b,PP c,PP d){
return check(a,c,d)*check(b,c,d)<0&&check(c,a,b)*check(d,a,b)<0;
}
struct P3{ld x,y,z;};
#define PP3 const P3&
#define rd(a) (P3){a.x,a.y,sqr(a.x)+sqr(a.y)}
P3 operator-(PP3 a,PP3 b){return (P3){a.x-b.x,a.y-b.y,a.z-b.z};}
ld operator|(PP3 a,PP3 b){return a.x*b.x+a.y*b.y+a.z*b.z;}
P3 operator&(PP3 a,PP3 b){return (P3){a.y*b.z-a.z*b.y,a.z*b.x-a.x*b.z,a.x*b.y-a.y*b.x};}
bool incir(PP a,PP b,PP c,PP d){
P3 aa=rd(a),bb=rd(b),cc=rd(c),dd=rd(d);
if(check(a,b,c)<0)std::swap(bb,cc);
return ((dd-aa)|((bb-aa)&(cc-aa)))<0;
}
int et,la[N],q[N],l,r,d[N],t,i,j,n,s;ld tmp;
struct E{int to,l,r;}e[N<<5];
#define add(x,y) (e[++et]=(E){y,la[x],0},e[e[et].l].r=la[x]=et)
void del(int x){
e[e[x].l].r=e[x].r,e[e[x].r].l=e[x].l;
if(la[e[x^1].to]==x)la[e[x^1].to]=e[x].l;
}
void work(int l,int r){int i,j,t=0,id,ld,rd,mid=l+r>>1,flag;
if(r-l<=2){
for(i=l;i<=r;i++)
for(j=i+1;j<=r;j++)add(i,j),add(j,i);
return;
}
work(l,mid),work(mid+1,r);
for(i=l;i<=r;q[++t]=i++)
while(t>1&&check(a[q[t-1]],a[q[t]],a[i])<0)t--;
for(i=1;i<t;i++)if(q[i]<=mid&&q[i+1]>mid)ld=q[i],rd=q[i+1];
for(add(ld,rd),add(rd,ld);;add(ld,rd),add(rd,ld)){
flag=0;
for(i=la[ld];i;i=e[i].l)
if(check(a[ld],a[rd],a[e[i].to])>0&&
(!flag||incir(a[ld],a[rd],a[id],a[e[i].to])))flag=-1,id=e[i].to;
for(i=la[rd];i;i=e[i].l)
if(check(a[rd],a[ld],a[e[i].to])<0&&
(!flag||incir(a[rd],a[ld],a[id],a[e[i].to])))flag=1,id=e[i].to;
if(!flag)return;
if(flag==-1){
for(i=la[ld];i;i=e[i].l)
if(cross(a[id],a[rd],a[ld],a[e[i].to]))del(i),del(i^1);ld=id;
}else{
for(i=la[rd];i;i=e[i].l)
if(cross(a[id],a[ld],a[rd],a[e[i].to]))del(i),del(i^1);rd=id;
}
}
}
#define M(a) memset(a,0,sizeof(a))
int main(){
for(t=F();t--;printf("%d\n",d[0])){
et=1,M(la),memset(d,63,sizeof(d));tmp=1e10;
n=F(),lim=gp(),o=gp();j=0;
for(i=1;i<=n;i++)if(cc=gp(),cc.x<=lim.x&&cc.y<=lim.y)a[++j]=cc;n=j;
std::sort(a+1,a+1+n);work(1,n);
for(i=1;i<=n;i++)if(dis2(o-a[i])<tmp)tmp=dis2(o-a[i]),s=i;
// for(i=1;i<=n;i++,puts(""))
// for(printf("%d: ",i),j=la[i];j;j=e[j].l)printf("%d ",e[j].to);
for(r=0,i=1;i<=n;q[++r]=i++)
while(r>1&&check(a[q[r-1]],a[q[r]],a[i])<0)r--;
for(i=1;i<r;i++)add(q[i],0);
for(r=0,i=n;i;q[++r]=i--)
while(r>1&&check(a[q[r-1]],a[q[r]],a[i])<0)r--;
for(i=1;i<r;i++)add(q[i],0);
for(q[l=r=0]=s,d[s]=0;l<=r;l++)
for(i=la[q[l]];i;i=e[i].l)
if(d[e[i].to]>d[q[l]]+1)d[q[++r]=e[i].to]=d[q[l]]+1;
}
}


半平面交

/**************************************************************
Problem: 3199
User: wjy1998
Language: C++
Result: Accepted
Time:344 ms
Memory:3992 kb
****************************************************************/

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
int aa;char ch;int F(){
while(ch=getchar(),ch<'0'||ch>'9');aa=ch-'0';
while(ch=getchar(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
#define sqr(x) ((x)*(x))
typedef double ld;
struct P{ld x,y;int n;}a[610],b1[610],b2[610],a0,a1,a2,a3,bo,s,rtt;
#define PP const P&
bool operator<(PP a,PP b){return a.x<b.x||a.x==b.x&&a.y<b.y;}
P operator+(PP a,PP b){return (P){a.x+b.x,a.y+b.y};}
P operator-(PP a,PP b){return (P){a.x-b.x,a.y-b.y};}
P operator/(PP a,ld b){return (P){a.x/b,a.y/b};}
P operator*(PP a,PP b){ld d=a.x*b.x,e=a.y*b.y,f=(a.x+a.y)*(b.x+b.y);return (P){d-e,f-e-d,a.n};}
ld operator&(PP a,PP b){return a.x*b.y-a.y*b.x;}
ld check(PP a,PP b,PP c){return (b-a)&(c-a);}
ld dis2(PP a){return sqr(a.x)+sqr(a.y);}
int _,n,i,j,d[610],et,la[610],l,r,q[1000],q1[1000],q2[1000];ld max_dis;
struct E{int to,nxt;}e[400010];
#define add(x,y) (e[++et]=(E){y,la[x]},la[x]=et)
P calc(PP p,PP v){//y=kx+b
ld k=v.y/v.x;
return (P){k,p.y-k*p.x};
}
P getjd(PP a,PP b){
ld x=-(b.y-a.y)/(b.x-a.x);
return (P){x,x*a.x+a.y};
}
#define ck(i) if(tmp.x*a[s].x+tmp.y<a[s].y)b1[++t1]=(P){tmp.x,-tmp.y,i};else b2[++t2]=(P){-tmp.x,tmp.y,i};
void work(int s){
int i,j,r1=0,r2=0,t1=0,t2=0,l1=1,l2=1,flag;P tmp;
for(i=1;i<=n;i++)if(i!=s){
tmp=calc((a[i]+a[s])/2,(a[i]-a[s])*(P){0,1});
ck(i);
}
tmp=a0;ck(0);tmp=a1;ck(0);
tmp=a2;ck(0);tmp=a3;ck(0);

std::sort(b1+1,b1+1+t1);b1[0].x=1e10;
for(i=1;i<=t1;i++)if(b1[i].x!=b1[i-1].x){
while(r1>1&&check(b1[q1[r1-1]],b1[q1[r1]],b1[i])<=0)r1--;q1[++r1]=i;
}
for(i=1;i<=t1;i++)b1[i].y=-b1[i].y;

std::sort(b2+1,b2+1+t2);b2[0].x=1e10;
for(i=1;i<=t2;i++)if(b2[i].x!=b2[i-1].x){
while(r2>1&&check(b2[q2[r2-1]],b2[q2[r2]],b2[i])<=0)r2--;q2[++r2]=i;
}
for(i=1;i<=t2;i++)b2[i].x=-b2[i].x;

//del_head
for(;;){flag=0;
if(l1<r1){
tmp=getjd(b1[q1[l1]],b1[q1[l1+1]]);
if(tmp.x*b2[q2[l2]].x+b2[q2[l2]].y<=tmp.y){
l1++;flag=1;
continue;
}
}
if(l2<r2){
tmp=getjd(b2[q2[l2]],b2[q2[l2+1]]);
if(tmp.x*b1[q1[l1]].x+b1[q1[l1]].y>=tmp.y){
l2++;flag=1;
continue;
}
}
if(flag==0)break;
}
//del_tail
for(;;){flag=0;
if(l1<r1){
tmp=getjd(b1[q1[r1-1]],b1[q1[r1]]);
if(tmp.x*b2[q2[r2]].x+b2[q2[r2]].y<=tmp.y){
r1--;flag=1;
continue;
}
}
if(l2<r2){
tmp=getjd(b2[q2[r2-1]],b2[q2[r2]]);
if(tmp.x*b1[q1[r1]].x+b1[q1[r1]].y>=tmp.y){
r2--;flag=1;
continue;
}
}
if(flag==0)break;
}
for(i=l1;i<=r1;i++)add(s,b1[q1[i]].n);
for(i=l2;i<=r2;i++)add(s,b2[q2[i]].n);
}
int main(){
rtt=(P){cos(1e-9),sin(1e-9)};
for(_=F();_--;printf("%d\n",d[0])){
n=F(),bo=(P){F(),F()},s=(P){F(),F()}*rtt;
a0=(P){0,0},a1=(P){bo.x,0},a2=bo,a3=(P){0,bo.y};
a1=a1*rtt,a2=a2*rtt,a3=a3*rtt;
a0=calc(a0,a1-a0);
a1=calc(a1,a2-a1);
a2=calc(a2,a3-a2);
a3=calc(a3,(P){0,0}-a3);
for(i=1;i<=n;i++)a[i]=(P){F(),F()}*rtt;
memset(la,0,sizeof(la)),et=1;
memset(d,63,sizeof(d));
std::sort(a+1,a+1+n);
for(i=1;i<=n;i++)work(i);
for(max_dis=1e10,i=1;i<=n;i++)
if(max_dis>dis2(s-a[i]))max_dis=dis2(s-a[i]),j=i;
for(q[l=r=0]=j,d[j]=0;l<=r;l++)
for(i=la[q[l]];i;i=e[i].nxt)
if(d[e[i].to]>d[q[l]]+1)
d[q[++r]=e[i].to]=d[q[l]]+1;
}
}


  评论这张
 
阅读(180)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018