88 条题解
-
0
victorygod LV 5 @ 2009-04-10 23:15:50
我记得代码不长啊,怎么到这里显得这么长？？
#include
#include
using namespace std;double f[30][5],a[30],b[30][5];
int n;bool check(int x1,int y1,int x2,int y2)
{
for (int i=x1+1;ib[i][2]&&yy=0) return f[x][y];
double s=10000000.23;
if (check(x,y,n+1,0)) return hypot(a[n+1]-a[x],abs(b[n+1][0]-b[x][y]));
for (int i=x+1;ib[i][1]>>b[i][2]>>b[i][3]>>b[i][4];
printf("%.2f\n",search(0,0));
return 0;
}
直接搜索……当然加了记忆化。本身就是dp，最开始时按搜索想的，就这么写了…… -
0
lijian3256 LV 10 @ 2009-04-09 13:22:40
发现我的代码写的又丑又长。。。
#include
#include
using namespace std;
const int MaxN = 100;struct Point
{
double x, y;
} P[MaxN];struct Line
{
double x, a, b;
} L[MaxN];
double G[MaxN][MaxN];
int N;
bool Used[MaxN];
double Ans[MaxN];double Dis(int a, int b)
{
return sqrt((P[a].x - P.x)*(P[a].x - P.x)+(P[a].y - P.y)*(P[a].y - P.y));
}double max(double a, double b)
{
if (a > b) return a;
else return b;
}double min(double a, double b)
{
if (a > b) return b;
else return a;
}double Multi(Point pt1, Point pt2, Point pt0)
{//向量的X乘，不是点乘
//pt0视为原点
//返回结果大于0pt1在PT2的在顺时针方向
// < 0在逆时针方向
// == 0两向量共线
double x1 = pt1.x - pt0.x;
double y1 = pt1.y - pt0.y;
double x2 = pt2.x - pt0.x;
double y2 = pt2.y - pt0.y;
return x1 * y2 - x2*y1;
}bool Chk(Line T, int a, int b)
{
Point p1, p2, q1, q2;
p1.x = T.x, p1.y = T.a;
p2.x = T.x, p2.y = T.b;
q1 = P[a];
q2 = P;
if (!(max(p1.x, p2.x) >= min(q1.x, q2.x) && max(q1.x, q2.x) >= min(p1.x, p2.x) &&
max(p1.y, p2.y) >= min(q1.y, q2.y) && max(q1.y, q2.y) >= min(p1.y, p2.y)))
return 0;
double t1 = Multi(q1, p2, p1);
double t2 = Multi(q2, p2, p1);
double t = t1*t2;
if (t > 0) return 0;
t1 = Multi(p1, q2, q1);
t2 = Multi(p2, q2, q1);
t = t1*t2;
if (t > 0) return 0;
return 1;
}bool Chk(int a, int b)
{
if (a != 0)
{
if ((a - 1) / 4 + 1 == (b - 1) / 4) return 1;
if ((a - 1) / 4 == (b - 1) / 4) return 0;
bool Flag = 0;
for (int i = (a - 1) / 4 + 1; i < (b - 1) / 4; i++)
if (!Chk(L[i * 2 + 1], a, b) && !Chk(L[i * 2 + 2], a, b))//判断a、b的是否和一段空的线段存在交点
{
Flag = 1;
break;
}
if (!Flag) return 1;
}
else
{
if ((b - 1) / 4 == 0) return 1;
bool Flag = 0;
for (int i = 0; i < (b - 1) / 4; i++)
if (!Chk(L[i * 2 + 1], a, b) && !Chk(L[i * 2 + 2], a, b))//判断a、b的是否和一段空的线段存在交点
{
Flag = 1;
break;
}
if (!Flag) return 1;
}
return 0;
}int main()
{
scanf("%d", &N);
for (int i = 0; i < N; i++)
{
double x, a1, a2, b1, b2;
scanf("%lf%lf%lf%lf%lf", &x, &a1, &b1, &a2, &b2);
P[i * 4 + 1].x = x, P[i * 4 + 1].y = a1;
P[i * 4 + 2].x = x, P[i * 4 + 2].y = b1;
P[i * 4 + 3].x = x, P[i * 4 + 3].y = a2;
P[i * 4 + 4].x = x, P[i * 4 + 4].y = b2;
L[i * 2 + 1].x = x, L[i * 2 + 1].a = a1, L[i * 2 + 1].b = b1;
L[i * 2 + 2].x = x, L[i * 2 + 2].a = a2, L[i * 2 + 2].b = b2;
}
P[0].x = 0, P[0].y = 5;
P[N * 4 + 1].x = 10, P[N * 4 + 1].y = 5;
for (int i = 0; i -
0
=。=||一次AC。。我的方法比较简单啊。。1.读入数据，把每个口的两个点用一个结构记录，每个点都记下来struct Node{ double x,y;}B[100];然后还要加上起点和终点。。把墙当作一条直线，struct Line{ double x,y1,y2;}C[100];2.然后就预处理，计算每个口上的点之间的距离，这里就要判断，这两个点之间的连线是否与某块墙有交点。。。3.然后就用最短路来求就对了。。。。
#include#includeusing namespace std;const long N=30;const double Max=100000000.0;double g[100][100];long n,m=0,Lnum=0;struct Wall{ double x,a1,b1,a2,b2;}A[N];struct Node{ double x,y;}B[100];struct Line{ double x,y1,y2;}C[100];void Input(){ freopen("p1013.in","r",stdin); scanf("%ld",&n); ++m;B[m].x=0;B[m].y=5; ++m;B[m].x=10;B[m].y=5; for(long i=1;i -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms提交了10来次，就因为忘了判断连线经过缺口的某个顶点时的情况了。
细节决定成败
写完了觉得还是不算难，就是构图时麻烦了点，最短路随便找个算法都行了，我用floyd都能秒杀。 -
0
帮忙看看哪儿有错啊，我觉得不会有问题么
用map存两点间距离，s存两点是否能直接相连，添加0和4*n+1两个点
用dijiskla算距离，最后输出map[0，4*n+1]
有错么？怎么只过两组？
var
map:array[0..500,0..500]of real;
s:array[0..500,0..500]of boolean;
n:integer;
{=============}
procedure init;
var i,j,k,a,b:integer;
x1,x2,x3,y1,y2,y3:real;
x,y:array[0..500]of real;
qiangx:array[1..200]of real;
qiangy:array[1..200,1..4]of real;
begin
readln(n);
for i:=1 to n do
begin
read(qiangx[i]);
for j:=1 to 4 do read(qiangy);
end;x[0]:=0;y[0]:=5;x[4*n+1]:=10;y[4*n+1]:=5;
for i:=1 to n do
for j:=1 to 4 do
begin
x[4*i-4+j]:=qiangx[i];
y[4*i-4+j]:=qiangy;
end;fillchar(s,sizeof(s),true);
for i:=0 to 4*n+1 do
for j:=i to 4*n+1 do
if (i+3)div 4 =(j+3)div 4 then s:=false
else begin
a:=(i+3)div 4;b:=(j+3)div 4;
x1:=x[i];x2:=x[j];
y1:=y[i];y2:=y[j];
for k:=a+1 to b-1 do
begin
x3:=qiangx[k];
y3:=y1+(y3-y1)*(y2-y1)/(x2-x1);
if not(( (y3>qiangy[k,1]) and (y3qiangy[k,3]) and (y3 -
0
加两面墙+o(4*(n+2))DP+枚举DP点与前面的所有点的可行性=o(n^2*20)的算法
=.......................秒杀？！？！？！？！
对于数据质疑中for i:=1 to n+1 do
for j:=1 to 4 do
begin
f:=99999;
for k:=i-1 downto 0 do
for l:=1 to 4 do
if able(i,j,k,l) then
begin
ff:=sqrt(sqr(x[i]-x[k])+sqr(y-y[k,l]));
f:=min(f,f[k,l]+ff);
end;
end;
end. -
0
huangzeyuand LV 3 @ 2008-09-22 20:00:48
real和extended有什么差别啊？要怎么用呢？为什么我用real错了第四个点，用了extended却错了第一和第五个点！！！
-
0
哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
victorygod
LV 5
@ 2009-04-10 23:15:50
