格斗游戏
Time Limit: 1000ms
Memory Limit: 65536KB
64-bit integer IO format: %lld Java class name: Main
Font Size:
Type: 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
大家知道，在格斗游戏中有各式各样的大招，因此大招的形状也是层出不穷。而在这些形状中，当然少不了圆这个完美的图形。
作为编写游戏的程序员，你需要判断玩家A放出的圆形大绝招与玩家B在同一个平面上时，是否能击中玩家B。
问题来了，如果给定玩家B和圆的位置，你能否知道玩家B是否被圆击中？当然，玩家B可能被完全击中，也可能只被击中身体的部分位置，也可能没有被击中。对于不同的击中程度，玩家B所损失的体力也不一样，因此你还要判断玩家B被击中的程度。为了简化问题，我们将玩家B的角色看作一条线段。
Input
第一行为N(N<=30)，表示数据组数。
每一组数据有两行，格式如下：
cx cy r
x1 y1 x2 y2
第一行为圆心的XY坐标和半径，第二行分别为线段两端点的XY坐标。
输入数据保证线段两端点不同，输入均为绝对值在100以内整数。
Output
对于每组数据，输出一行，表示如下关系的一种：
ALL IN ：线段完全在圆的内部或圆上，即没有严格在圆外的部分
PART IN ：线段有一些部分严格在圆内，也有一些部分严格在圆外
ALL OUT ：线段完全在圆的外部或圆上，即没有严格在圆内的部分
Sample Input
30 0 10 0 0 10 0 10 0 1 10 0 11 0 1 1
Sample Output
ALL INPART INALL OUT
Source
Author
1 #include2 #include 3 #include 4 using namespace std; 5 6 int dist2 (int x1, int y1, int x2, int y2) 7 { 8 return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1); 9 }10 11 int pointPro (int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4)12 {13 return (x2 - x1) * (x4 - x3) + (y2 - y1) * (y4 - y3);14 }15 16 int work (int x0, int y0, int r, int x1, int y1, int x2, int y2)//圆坐标和半径,线段的两个端点17 {18 int A, B, C, OA2, OB2, R2;19 A = y2 - y1;20 B = x1 - x2;21 C = x2 * y1 - x1 * y2;22 R2 = r * r;23 if ((A * x0 + B * y0 + C) * (A * x0 + B * y0 + C) >= R2 * (A * A + B * B))24 return 1;//没有严格在里面 （圆外）25 OA2 = dist2 (x0, y0, x1, y1);26 OB2 = dist2 (x0, y0, x2, y2);27 if (OA2 <= R2 && OB2 <= R2)28 return -1;//没有严格在外面 （圆内）29 if (OA2 > R2 && OB2 < R2 || OA2 < R2 && OB2 > R2)30 return 0;31 if (pointPro (x0, y0, x1, y1, x1, y1, x2, y2) * pointPro (x0, y0, x2, y2, x2, y2, x1, y1) < 0)32 return 1;33 else34 return 0;35 }36 37 38 int main()39 {40 int t;41 int cx,cy,r,x1,x2,y1,y2;42 while(scanf("%d",&t)>0)43 {44 while(t--)45 {46 scanf("%d%d%d",&cx,&cy,&r);47 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);48 int hxl=work(cx,cy,r,x1,y1,x2,y2);49 if(hxl==1) printf("ALL OUT\n");50 else if(hxl==-1) printf ("ALL IN\n");51 else printf ("PART IN\n");52 }53 }54 return 0;55 }