[NOI2011] 스마트카 경기(계산 기하학+동적 기획)
경로는 직사각형 정점에서만 모퉁이를 돌 수 있기 때문에 4*n+2개의 점을 건설할 수 있다. 최단로를 구하려면 어떤 점이 직접 연결될 수 있는지 판단하기만 하면 된다.
직접 매거점 대 병합 도면, 복잡도 O(n^3), 최적화: 매거점 u와 다른 모든 점이 연결될 수 있을 때 천연적인 단조성을 이용할 수 있다. 이런 점의 가로 좌표는 왼쪽에서 오른쪽이다.
왼쪽에서 오른쪽 매거점 u, u로 최단로를 업데이트합니다. 각 u에 대해 위에서 아래로 시선(두 방향)을 유지하고 다른 점 v의 매거진은 여전히 왼쪽에서 오른쪽으로 추진됩니다.
이렇게 하면 u, v가 라인으로 연결될 수 있는지 판단하려면 v가 현재 시야(벡터 포크)에 있는지 판단하면 된다.
최단선은 전문적으로 구하지 않고 시야를 유지하는 과정에서 O(n^2)를 구한다.
【코드】
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define INF 1000000000
double d[8010]={0};
int x_1[2010]={0},y_1[2010]={0},x_2[2010]={0},y_2[2010]={0},x[8010]={0},y[8010]={0},pla[8010]={0};
int tot=0;
void jh(int* a,int* b)
{
int t=*a;
*a=*b;
*b=t;
}
double dis(int x1,int y1,int x2,int y2)
{
return sqrt( (double)((x1-x2)*(x1-x2))+(double)((y1-y2)*(y1-y2)) );
}
int cross(int x1,int y1,int x2,int y2)
{
return x1*y2-x2*y1;
}
void update(int s)
{
int i=s,xu=x[s],yu=y[s]+1,xd=x[s],yd=y[s]-1;// x
while(i>1&&x[i]==x[i-1]) i--;
for(;i<=tot;i++)
{
if(cross(xd-x[s],yd-y[s],x[i]-x[s],y[i]-y[s])>=0&&cross(xu-x[s],yu-y[s],x[i]-x[s],y[i]-y[s])<=0)// :
if(d[i]>d[s]+dis(x[s],y[s],x[i],y[i])) d[i]=d[s]+dis(x[s],y[s],x[i],y[i]);
if(pla[i]!=0&&(x[s]!=x[i]||y[s]!=y[i]))// ( :i ; i s : )
{
if(pla[i]==2&&cross(xu-x[s],yu-y[s],x[i]-x[s],y[i]-y[s])<=0)//
{
xu=x[i];
yu=y[i];
}
if(pla[i]==1&&cross(xd-x[s],yd-y[s],x[i]-x[s],y[i]-y[s])>=0)//
{
xd=x[i];
yd=y[i];
}
}
if(cross(xd-x[s],yd-y[s],xu-x[s],yu-y[s])<0) return;
}
}
int main()
{
double v;
int n,i,xs,ys,xt,yt,tou,wei,t;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d%d%d%d",&x_1[i],&y_1[i],&x_2[i],&y_2[i]);
scanf("%d%d%d%d",&xs,&ys,&xt,&yt);
scanf("%lf",&v);
if(xs>xt)
{
jh(&xs,&xt);
jh(&ys,&yt);
}
for(tou=1;tou<=n;tou++)// s
if(xs<=x_2[tou]&&y_1[tou]<=ys&&ys<=y_2[tou]) break;
for(wei=n;wei>=1;wei--)// t
if(x_1[wei]<=xt&&y_1[wei]<=yt&&yt<=y_2[wei]) break;
x[0]=xs;
y[0]=ys;
for(i=tou;i<=wei;i++)
{
if(x_1[i]==xt&&y_1[i]<=yt&&yt<=y_2[i])//t i ( ) ,
{
x[++tot]=xt;
y[tot]=yt;
t=tot;
}
x[++tot]=x_1[i];
y[tot]=y_1[i];
pla[tot]=1;//1 ( )
x[++tot]=x_1[i];
y[tot]=y_2[i];
pla[tot]=2;//2 ( )
if(x_1[i]<xt&&xt<=x_2[i]&&y_1[i]<=yt&&yt<=y_2[i])//t i
{
x[++tot]=xt;
y[tot]=yt;
t=tot;
}
x[++tot]=x_2[i];
y[tot]=y_1[i];
pla[tot]=1;//1 ( )
x[++tot]=x_2[i];
y[tot]=y_2[i];
pla[tot]=2;//2 ( )
}
for(i=1;i<=tot;i++)
d[i]=INF;
for(i=0;i<=tot;i++)
update(i);
printf("%.10lf",d[t]/v);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.