TOJ 4080 find the princessIII（圆和直线相交）
Time Limit: 1.0 Seconds Memory Limit:65536K
Total Runs: 613 Accepted Runs:118 </center>
It is a pity that the Dsir cost much time in "find the princess II". The devil has dropped a bomb beside the princess.This is the scope of bomb is a circle. The radius of the circle is R. The bomb can be regarded as a point. The coordinates of cirle is (cx, cy). For this problem,we can assume that the princess was tied to a stick. The coordinates of stick two endpoints is (x1, y1), (x2,y2). Dsir want to know whether the princess would be Fried.
Input
First line of input T(the number of cases), each line of input cx, cy, R, x1, y1, x2, y2.
-100≤cx≤100,-100≤cy≤100,-100≤x1≤100, -100≤y1≤100, -100≤x2≤100, -100≤y2≤100, -100≤R≤100
Output
For each case, output "All in"(the princess completely within the circle) OR "Part in"(the princess parts within the circle) OR "All out"(the princess not in the circle).
Hint:
If stick with only one point on the circle, is considered to be the princess is not in the circle!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
#include<string>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const double eps=1e-7;
int sgn(double x)
{
if(x<-eps)return -1;
if(x>eps)return 1;
return 0;
}
typedef struct vec
{
double x,y;
vec(double xa,double ya)
{
x=xa,y=ya;
}
vec operator - (vec v)
{
return vec(x-v.x,y-v.y);
}
double operator * (vec v)
{
return x*v.x+y*v.y;
}
double len()
{
//printf("%f %f %f\n",x,y,hypot(x,y));
return hypot(x,y);
}
}vec;
double cross(vec a,vec b)
{
return a.x*b.y-a.y*b.x;
}
double dist_point_to_segment(vec p,vec a,vec b)
{
if(sgn((p-a)*(b-a))>=0&&sgn((p-b)*(a-b))>=0)return fabs(cross(p-a,b-a))/(b-a).len();
return min((p-a).len(),(p-b).len());
}
int main()
{
double xa,ya,xb,yb,xc,yc,R;
int T;
scanf("%d",&T);
while(T--)
{
scanf("%lf%lf%lf%lf%lf%lf%lf",&xc,&yc,&R,&xa,&ya,&xb,&yb);
double dist=dist_point_to_segment(vec(xc,yc),vec(xa,ya),vec(xb,yb));
double dist2=max(vec(xa-xc,ya-yc).len(),vec(xb-xc,yb-yc).len());
//printf("%f %f %f\n",dist,dist2,R);
if(dist2<=R+eps)
{
printf("All in\n");
}
else
{
if(dist+eps>R)
{
//printf("%f %f \n",dist+eps,R);
printf("All out\n");
}
else printf("Part in\n");
}
//if(T)printf("\n");
}
}
投递阅文集团等公司10个岗位 >