Problem A: Return of the Jedi
时间： 1ms 内存：128M
描述：
Problem A: Return of the Jedi
Luke Skywalker races through the forest on a speeder bike, trying to outrun a patrol of Imperial scouts on Endor. A small moon near a new Death Star, Endor is covered by dense foliage and a thick forest of ancient towering trees. The speeder bike , which Luke stole from an Imperial scout, is an antigravity vehicle capable of speeds of 200 miles an hour. How quickly can Luke reach Princess Leia in the Ewok village?
The forest is a plane with T trees. Luke's position is specified by a pair of coordinates ( xluke , yluke ) within the plane. The Ewok village has coordinates ( xewok , yewok ). You are to find the shortest travel time from Luke's position to the Ewok village.
The first line of input contains T, xluke , yluke xewok , yewok . T lines follow; each gives the coordinates and diameter of a tree: xtreei , ytreei , dtreei . T is an integer not exceeding 10; coordinates and diameters are real numbers in miles. Trees do not intersect or touch one another.
Output is a single real number, to two decimal places, giving the minimum travel time in seconds.
输入：
输出：
示例输入：
2 0.0 0.0 10.0 0.0
4.0 0.0 1.0
6.0 0.0 1.0
示例输出：
181.13
提示：
参考答案（内存最优[2916]）：
/*
* sadf.cc
*
* Created on: 2010-4-29
* Author: teacher
*/
#include <stdio.h>
#include <map>
#include <math.h>
using namespace std;
map <unsigned,unsigned> M;
unsigned long
times (unsigned long a, unsigned long b, unsigned long m){
return (unsigned long long) a * b % m;
}
unsigned long
power (unsigned long val, unsigned long power, unsigned long m){
unsigned long acc = 1;
unsigned long p;
for (p = power; p ; p=p>>1) {
if (p & 1) acc = times(acc, val, m);
val = times(val, val, m);
}
return acc;
}
int main(){
unsigned P,B,L,N;
unsigned i,j,k,m,n;
unsigned jump;
while (scanf("%d %d %d",&P,&B,&N) == 3) {
M.clear();
jump = sqrt(P);
for (i=0;i<jump && i < P-1;i++){
M[power(B,i,P)] = i+1;
}
for (i=0;i<P-1;i+=jump){
if (j = M[times(N,power(B,P-1-i,P),P)]) {
j--;
L = (i+j)%(P-1);
if (power(B,L,P) != N) printf("***oops*** %d %d ",i,j);
printf("%d\n",L);
goto done;
}
}
printf("no solution\n");
done:;
}
return 0;
}
/**************************************************************
Problem: 1269
User: zhblue
Language: C++
Result: Compile Error
****************************************************************/
参考答案（时间最优[20]）：
/*
============================================================================
Name : tests.c
Author :
Version :
Copyright : Your copyright notice
Description : Hello World in C, Ansi-style
============================================================================
*/
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
double x[100], y[100], r[100];
double xp[1000], yp[1000]; int tree[1000];
int i,j,k, np, T;
double D, E, F, dx, dy, rdx, rdy, theta, phi;
double adj[1000][1000]; int derv[1000][1000];
void linepoints(double x1, double y1, double x2, double y2,
double *a, double *b, double *c) {
*a = y2 - y1;
*b = x1 - x2;
*c = *a * x1 + *b * y1;
}
double distpointline(double x, double y, double a, double b, double c) {
return fabs(a*x + b*y - c)/sqrt(a*a + b*b);
}
double sqdist(double a, double b, double c, double d){
return (a-c)*(a-c) + (b-d)*(b-d);
}
void check(int i, int j, double xj, double yj, double xi, double yi){
int k;
double a,b,c,d;
double dot1 = (xj-x[j])*(xj-xi) + (yj-y[j])*(yj-yi);
double dot2 = (xi-x[i])*(xi-xj) + (yi-y[i])*(yi-yj);
//printf("check %d %d %lf %lf : %lf %lf %lf %lf\n",i,j,dot2,dot1,xi,yi,xj,yj);
linepoints(xi,yi,xj,yj,&a,&b,&c);
for (k = 0; k<T; k++){
if (k == i || k == j) continue;
if (distpointline(x[k],y[k],a,b,c) > r[k]) continue;
if ((x[k]-xi)*(xj-xi)+(y[k]-yi)*(yj-yi) < 0) continue;
if ((x[k]-xj)*(xi-xj)+(y[k]-yj)*(yi-yj) < 0) continue;
//printf(" ... rejected by circle %d\n",k);
return;
}
adj[np][np+1] = adj[np+1][np] = hypot(xi-xj,yi-yj);
tree[np] = j;
xp[np] = xj;
yp[np++] = yj;
tree[np] = i;
xp[np] = xi;
yp[np++] = yi;
}
int main(){
double x1a, x1b, x1c, x1d, x2a, x2b, x2c, x2d, y1a, y1b,y1c, y1d, y2a, y2b, y2c, y2d;
scanf("%d%lf%lf%lf%lf",&T,&x[0],&y[0],&x[1],&y[1]);
r[0] = r[1] = 0;
T += 2;
for (i=2;i<T;i++) {
scanf("%lf%lf%lf",&x[i],&y[i],&r[i]);
r[i] /= 2;
}
xp[np] = x[0];
yp[np++] = y[0];
tree[np]=1;
xp[np] = x[1];
yp[np++] = y[1];
for (i=0;i<T;i++) for (j=0;j<T;j++) {
if (r[i] > r[j] || r[i]==r[j] && i>=j) continue;
D = hypot(x[i]-x[j], y[i]-y[j]);
theta = asin((r[j]-r[i])/D);
E = D * cos(theta);
phi = atan(r[i]/E);
F = E / cos(phi);
dx = (x[j] - x[i]) * F/D;
dy = (y[j] - y[i]) * F/D;
rdx = cos(theta+phi) * dx - sin(theta+phi) * dy;
rdy = sin(theta+phi) * dx + cos(theta+phi) * dy;
x1a = x[i] + rdx;
y1a = y[i] + rdy;
rdx = cos(-theta-phi) * dx - sin(-theta-phi) * dy;
rdy = sin(-theta-phi) * dx + cos(-theta-phi) * dy;
x1b = x[i] + rdx;
y1b = y[i] + rdy;
dx = (x[j] - x[i]) * r[i]/D;
dy = (y[j] - y[i]) * r[i]/D;
rdx = cos(theta+M_PI/2) * dx - sin(theta+M_PI/2) * dy;
rdy = sin(theta+M_PI/2) * dx + cos(theta+M_PI/2) * dy;
x2a = x[i] + rdx;
y2a = y[i] + rdy;
rdx = cos(-theta-M_PI/2) * dx - sin(-theta-M_PI/2) * dy;
rdy = sin(-theta-M_PI/2) * dx + cos(-theta-M_PI/2) * dy;
x2b = x[i] + rdx;
y2b = y[i] + rdy;
// Case 2: tangent passes between centres
D = hypot(x[i]-x[j], y[i]-y[j]);
theta = asin((r[i]+r[j])/D);
E = D * cos(theta);
phi = atan(r[i]/E);
F = E / cos(phi);
dx = (x[j] - x[i]) * F/D;
dy = (y[j] - y[i]) * F/D;
rdx = cos(theta-phi) * dx - sin(theta-phi) * dy;
rdy = sin(theta-phi) * dx + cos(theta-phi) * dy;
x1c = x[i] + rdx;
y1c = y[i] + rdy;
rdx = cos(-theta+phi) * dx - sin(-theta+phi) * dy;
rdy = sin(-theta+phi) * dx + cos(-theta+phi) * dy;
x1d = x[i] + rdx;
y1d = y[i] + rdy;
dx = (x[j] - x[i]) * r[i]/D;
dy = (y[j] - y[i]) * r[i]/D;
rdx = cos(theta-M_PI/2) * dx - sin(theta-M_PI/2) * dy;
rdy = sin(theta-M_PI/2) * dx + cos(theta-M_PI/2) * dy;
x2c = x[i] + rdx;
y2c = y[i] + rdy;
rdx = cos(-theta+M_PI/2) * dx - sin(-theta+M_PI/2) * dy;
rdy = sin(-theta+M_PI/2) * dx + cos(-theta+M_PI/2) * dy;
x2d = x[i] + rdx;
y2d = y[i] + rdy;
check(i,j,x1a,y1a,x2a,y2a);
check(i,j,x1b,y1b,x2b,y2b);
check(i,j,x1c,y1c,x2c,y2c);
check(i,j,x1d,y1d,x2d,y2d);
}
for (i=0;i<np;i++) for (j=0;j<np; j++) {
if (i == j || adj[i][j]) continue;
if (tree[i] != tree[j]) {
adj[i][j] = 1e99;
} else {
double xx = x[tree[i]];
double yy = y[tree[i]];
double rr = r[tree[i]];
double costheta = ((xp[i]-xx)*(xp[j]-xx)+(yp[i]-yy)*(yp[j]-yy)) / (rr*rr);
double theta = acos(costheta);
double d = theta * rr;
if (rr == 0) continue;
adj[i][j] = d;
}
}
for (i=0;i<np;i++) for (j=0;j<np; j++) {
if (adj[i][j] > 1e98) continue;
//printf("edge %d %d %lf %lf %lf %lf (%lf)\n",tree[i],tree[j],xp[i],yp[i],xp[j],yp[j],adj[i][j]);
}
for (i=0;i<np;i++)for(j=0;j<np;j++)for(k=0;k<np;k++){
if (adj[j][i]+adj[i][k] < adj[j][k]) {
adj[j][k] = adj[j][i]+adj[i][k];
derv[j][k] = i;
}
}
printf("%0.2lf\n",adj[0][1]*3600/200, adj[0][1]);
//printderv(0,1);
return 0;
}
void printderv(int i, int j){
double r1, r2;
if (i == j) return;
if (!derv[i][j]) {
printf("derv %lf %lf (tree %d)-> %lf %lf (tree %d) (%lf) \n",xp[i],yp[i],tree[i],xp[j],yp[j],tree[j],adj[i][j]);
}else{
printderv(i,derv[i][j]);
printderv(derv[i][j],j);
}
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。