夜空中最亮的星
showpid=34977" class="ui-button ui-widget ui-state-default ui-corner-all ui-button-text-only" style="margin:0px 0.1em 0px -1px; padding:0px; text-decoration:none; font-family:'Trebuchet MS',Helvetica,Arial,sans-serif; font-size:1.1em; border:1px solid rgb(204,204,204); background-color:rgb(238,238,238); font-weight:bold; color:rgb(68,68,68); display:inline-block; position:relative; zoom:1; overflow:visible">Status
Statistics Discuss Next+
-
None Graph Theory
2-SAT Articulation/Bridge/Biconnected Component
Cycles/Topological Sorting/Strongly Connected Component
Shortest Path
Bellman Ford Dijkstra/Floyd Warshall
Euler Trail/Circuit
Heavy-Light Decomposition
Minimum Spanning Tree
Stable Marriage Problem
Trees
Directed Minimum Spanning Tree
Flow/Matching Graph Matching
Bipartite Matching
Hopcroft–Karp Bipartite Matching
Weighted Bipartite Matching/Hungarian Algorithm
Flow
Max Flow/Min Cut
Min Cost Max Flow
DFS-like Backtracking with Pruning/Branch and Bound
Basic Recursion
IDA* Search Parsing/Grammar
Breadth First Search/Depth First Search
Advanced Search Techniques
Binary Search/Bisection
Ternary Search
Geometry
Basic Geometry Computational Geometry
Convex Hull
Pick's Theorem Game Theory
Green Hackenbush/Colon Principle/Fusion Principle
Nim
Sprague-Grundy Number
Matrix Gaussian Elimination
Matrix Exponentiation
Data Structures
Basic Data Structures
Binary Indexed Tree
Binary Search Tree
Hashing Orthogonal Range Search
Range Minimum Query/Lowest Common Ancestor
Segment Tree/Interval Tree
Trie Tree
Sorting Disjoint Set
String
Aho Corasick Knuth-Morris-Pratt
Suffix Array/Suffix Tree
Math
Basic Math Big Integer Arithmetic
Number Theory
Chinese Remainder Theorem
Extended Euclid
Inclusion/Exclusion
Modular Arithmetic
Combinatorics Group Theory/Burnside's lemma
Counting
Probability/Expected Value
Others Tricky
Hardest Unusual
Brute Force
Implementation Constructive Algorithms
Two Pointer
Bitmask Beginner
Discrete Logarithm/Shank's Baby-step Giant-step Algorithm
Greedy
Divide and Conquer
Dynamic Programming
Tag it!
想要在陌生的地方不迷路。分清楚方向是非常重要的。看星星就是一个非常好的辅助方法。
在一段时间内每晚的同一时间，天上星星的排布是差点儿不变的。
每颗星星的亮暗程度都有一个标识。称为星等。用一个实数来表示。
这个实数的值越小，代表星星越亮，在灯光明亮的城市中能看到的星星的星等范围为
- ~ 3.5等左右。
Map同学害怕丢掉Map这个称号，每晚都勤劳地记下当天帝都星星的排布情况。他面向正北方向站立，将看到的天空映射到一张巨大的直角坐标系上，那么每颗星星都拥有了一个坐标。
这天Map同学来到了漂亮的哈尔滨，抬头看见了最亮的星星木星和第二亮的北河三。他朝向他以为的北方站立。像在帝都一样地计算出它们的坐标。
但实际上他并非总能凭直觉找到北的。并且对于使用的坐标系的刻度的大小也没有办法把握。
那么如今他想知道。最少须要转多少角度，他才可以面向正北。
Input
第一行为数据组数t(t<=1000)。
接下来，对每组数据：
第一行为n(2<=n<=1000)。表示前一天在帝都看到的星星的数量。
下面为n行，每行3个实数，分别为n颗星星的坐标和星等。
最后一行为4个实数，分别为木星和北河三的坐标。
以上实数绝对值不超过1000。π取3.14159265358。
Output
输出一行，为所须要转的最小角度。保留3位小数。
Sample Input
1
2
0 0 -2
1 0 0
0 0 0 1.2
Sample Output
90.000
Source
pid=34977#" class="submitprob ui-button ui-widget ui-state-default ui-corner-all ui-button-text-only" style="margin:0px 0.1em 0px -1px; padding:0px; text-decoration:none; font-family:'Trebuchet MS',Helvetica,Arial,sans-serif; font-size:1.1em; border:1px solid rgb(204,204,204); background-color:rgb(238,238,238); font-weight:bold; color:rgb(68,68,68); display:inline-block; position:relative; zoom:1; overflow:visible">Submit
Status Statistics Discuss Next#include<stdio.h>
#include<math.h>
#define PI 3.14159265358
typedef struct nnn
{
double x,y,d;
}node;
int main()
{
int t,n;
double s,jd,x,y,dis[2];
node star[2],st[2],xl[2];
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
jd=10000;
star[0].d=star[1].d=10000;
for(int i=0;i<n;i++)
{
scanf("%lf%lf%lf",&x,&y,&s);
if(s<star[0].d)
{
star[1].x=star[0].x;
star[1].y=star[0].y;
star[1].d=star[0].d;
star[0].x=x; star[0].y=y; star[0].d=s;
}
else if(s<star[1].d)
{
star[1].x=x; star[1].y=y; star[1].d=s;
}
}
for(int i=0;i<2;i++)
scanf("%lf%lf",&st[i].x,&st[i].y);
xl[0].x=star[0].x-star[1].x;
xl[0].y=star[0].y-star[1].y;
dis[0]=sqrt(xl[0].x*xl[0].x+xl[0].y*xl[0].y); xl[1].x=st[0].x-st[1].x;
xl[1].y=st[0].y-st[1].y;
dis[1]=sqrt(xl[1].x*xl[1].x+xl[1].y*xl[1].y);
jd=180.0/PI*acos((xl[0].x*xl[1].x+xl[0].y*xl[1].y)/(dis[0]*dis[1]));
if(jd>180)jd=360-jd;
printf("%.3lf\n",jd);
}
}