格斗游戏
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
Tag it!
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!
大家知道，在格斗游戏中有各式各样的大招，因此大招的形状也是层出不穷。而在这些形状中，当然少不了圆这个完美的图形。
作为编写游戏的程序员，你需要判断玩家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
3
0 0 1
0 0 0 1
0 0 1
0 0 1 1
0 0 1
1 0 1 1
Sample Output
ALL IN
PART IN
ALL OUT
Source
Author
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std; int dist2 (int x1, int y1, int x2, int y2)
{
return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
} int pointPro (int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4)
{
return (x2 - x1) * (x4 - x3) + (y2 - y1) * (y4 - y3);
} int work (int x0, int y0, int r, int x1, int y1, int x2, int y2)//圆坐标和半径,线段的两个端点
{
int A, B, C, OA2, OB2, R2;
A = y2 - y1;
B = x1 - x2;
C = x2 * y1 - x1 * y2;
R2 = r * r;
if ((A * x0 + B * y0 + C) * (A * x0 + B * y0 + C) >= R2 * (A * A + B * B))
return ;//没有严格在里面 （圆外）
OA2 = dist2 (x0, y0, x1, y1);
OB2 = dist2 (x0, y0, x2, y2);
if (OA2 <= R2 && OB2 <= R2)
return -;//没有严格在外面 （圆内）
if (OA2 > R2 && OB2 < R2 || OA2 < R2 && OB2 > R2)
return ;
if (pointPro (x0, y0, x1, y1, x1, y1, x2, y2) * pointPro (x0, y0, x2, y2, x2, y2, x1, y1) < )
return ;
else
return ;
} int main()
{
int t;
int cx,cy,r,x1,x2,y1,y2;
while(scanf("%d",&t)>)
{
while(t--)
{
scanf("%d%d%d",&cx,&cy,&r);
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
int hxl=work(cx,cy,r,x1,y1,x2,y2);
if(hxl==) printf("ALL OUT\n");
else if(hxl==-) printf ("ALL IN\n");
else printf ("PART IN\n");
}
}
return ;
}