首页 > ACM题库 > HDU-杭电 > HDU 3158-PropBot[解题报告]HOJ
2014
03-06

HDU 3158-PropBot[解题报告]HOJ

PropBot

问题描述 :

You have been selected to write the navigation module for PropBot. Unfortunately, the mechanical engineers have not provided a lot of flexibility in movement; indeed, the PropBot can only make two distinct movements. It can either move 10 cm forward, or turn towards the right by 45 degrees. Each of these individual movements takes one second of time.

输入:

Your module has two inputs: the Cartesian coordinates of a point on the plane that the PropBot wants to get as close to as possible, and the maximum number of seconds that can be used to do this. At the beginning of the navigation, the robot is located at the origin, pointed in the +x direction.

The number of seconds will be an integer between 0 and 24, inclusive. Both the x and y coordinates of the desired destination point will be a real number between -100 and 100, inclusive.

The first entry in the input file will be the number of test cases, t (0 < t <= 100). Following this line will be t lines, with each line containing three entries separated by spaces. The first entry will be the number of seconds PropBot has to get close to the point. The second entry is the x-coordinate of the point, and the third entry is the y-coordinate of the point.

输出:

Your module has two inputs: the Cartesian coordinates of a point on the plane that the PropBot wants to get as close to as possible, and the maximum number of seconds that can be used to do this. At the beginning of the navigation, the robot is located at the origin, pointed in the +x direction.

The number of seconds will be an integer between 0 and 24, inclusive. Both the x and y coordinates of the desired destination point will be a real number between -100 and 100, inclusive.

The first entry in the input file will be the number of test cases, t (0 < t <= 100). Following this line will be t lines, with each line containing three entries separated by spaces. The first entry will be the number of seconds PropBot has to get close to the point. The second entry is the x-coordinate of the point, and the third entry is the y-coordinate of the point.

样例输入:

2
24 5.0 5.0
9 7.0 17.0

样例输出:

0.502525
0.100505

/**
 * ID: ping128
 * LANG: C++
 */

#include <stdio.h>
#include <iostream>
#include <sstream>
#include <stdlib.h>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <math.h>
#include <algorithm>
#include <map>
#include <string.h>

using namespace std;

typedef long long LL;
typedef pair<double, double>PII;
typedef pair<PII, int>PII2;

double dis(double x1, double y1, double x2, double y2)
{
 double xx = x1 - x2;
 double yy = y1 - y2;
 return sqrt(xx * xx + yy * yy);
}

double cx, cy, di;

#define PI 3.141592654
void go()
{
 cx += 10.0 * cos((di / 180.0) * (PI));
 cy += 10.0 * sin((di / 180.0) * (PI));
}

map<int, vector<PII> >pos;

int in[4];
vector<int> turn;

bool cmp2(double a, double b)
{
 return a > b;
}

void search2(int at, int num_turn, int sss, double x, double y)
{
 if(at == sss)
 {
 pos[num_turn].push_back(PII(x, y));
 }
 else
 {
 if(at == 0)
 {
 num_turn = -turn[at];
 }
 else
 {
 num_turn += turn[at - 1] - turn[at];
 }
 
 for(int i = 1; num_turn + i <= 24; i++ )
 {
 x += 10.0 * cos(((double)turn[at] * 45.0 / 180.0) * (PI));
 y += 10.0 * sin(((double)turn[at] * 45.0 / 180.0) * (PI));
 search2(at + 1, num_turn + i, sss, x, y);
 }
 }
}

void cal()
{
 sort(turn.begin(), turn.end(), cmp2);
 // for(int i = 0; i < turn.size(); i++ ) printf("%d ", turn[i]);
 // printf("\n");
 search2(0, 0, turn.size(), 0.0, 0.0);
}

void search(int at)
{
 if(at == 4)
 {
 turn.clear();
 for(int i = 0; i < 4; i++ )
 {
 if(in[i] == 1)
 {
 turn.push_back(-i);
 }
 else if(in[i] == 2)
 {
 turn.push_back(-i - 4);
 }
 }
 cal();
 }
 else
 {
 for(int i = 0; i < 3; i++ )
 {
 in[at] = i;
 search(at + 1);
 }
 }
}

class Solve
{
 public:
 void main2()
 {
 search(0);
 }
};

int main()
{
 // freopen("j.in", "r", stdin);
 // freopen(".out", "w", stdout);

 Solve ___test;
 ___test.main2();
 
 int Test;
 scanf("%d", &Test);
 for(int t = 1; t <= Test; t++ )
 {
 double dx, dy;
 int n;
 cin >> n >> dx >> dy;
 double maxx = dis(0.0, 0.0, dx, dy);
 for(int k = 0; k <= n; k++ )
 {
 int ss = pos[k].size();
 for(int j = 0; j < ss; j++ )
 {
 maxx = min(maxx, dis(pos[k][j].first, pos[k][j].second, dx, dy));
 }
 }
 printf("%.6lf\n", maxx);
 }
//while(1);
return 0;
}

  1. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  2. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

  3. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。