2014
03-06

# 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. 前几天徒步，路上脚磨起泡，身体疲惫，晚上错过酒店没有住宿点，背包准备失误太重，队友埋怨哭泣等等等等，麻烦太多了可以让人生气火大的地方太多了，但是我们都坚持下来了，没有中途而废。

3. 前几天徒步，路上脚磨起泡，身体疲惫，晚上错过酒店没有住宿点，背包准备失误太重，队友埋怨哭泣等等等等，麻烦太多了可以让人生气火大的地方太多了，但是我们都坚持下来了，没有中途而废。

4. 前几天徒步，路上脚磨起泡，身体疲惫，晚上错过酒店没有住宿点，背包准备失误太重，队友埋怨哭泣等等等等，麻烦太多了可以让人生气火大的地方太多了，但是我们都坚持下来了，没有中途而废。

5. 前几天徒步，路上脚磨起泡，身体疲惫，晚上错过酒店没有住宿点，背包准备失误太重，队友埋怨哭泣等等等等，麻烦太多了可以让人生气火大的地方太多了，但是我们都坚持下来了，没有中途而废。

6. 前几天徒步，路上脚磨起泡，身体疲惫，晚上错过酒店没有住宿点，背包准备失误太重，队友埋怨哭泣等等等等，麻烦太多了可以让人生气火大的地方太多了，但是我们都坚持下来了，没有中途而废。

7. 前几天徒步，路上脚磨起泡，身体疲惫，晚上错过酒店没有住宿点，背包准备失误太重，队友埋怨哭泣等等等等，麻烦太多了可以让人生气火大的地方太多了，但是我们都坚持下来了，没有中途而废。

8. 前几天徒步，路上脚磨起泡，身体疲惫，晚上错过酒店没有住宿点，背包准备失误太重，队友埋怨哭泣等等等等，麻烦太多了可以让人生气火大的地方太多了，但是我们都坚持下来了，没有中途而废。

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

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

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