2013
12-23

# Where is the little Jgshining?

When Jgshining is a baby, he already showed his high intelligence. For example ,when somebody asked him“Who do you love, Dad? Mom?”,He always answered:“Both!”.When he stayed together with Mom, Dad and brother, he always selects a position from where it is the same distance to all three people. Now, you are given the positions of dad, mom and brother, please print the point where Jgshining will select?
If there is no this kind of position, please output “No this position”, otherwise, you should print this point.

Input contains an integer N in the first line, which indicates the number of test data. And then N lines follow. Each line consists of three pairs of numbers xi and yi, separated by a space.

For each test data you should output the point where Jgshining will select,please output the point which has minimal distance from three people if more than one point satisfy the question. One line per case.

2
0 0 1 0 0 1
0 0 1 0 2 0

0.5 0.5
No this position

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <cassert>
#include <set>
#include <sstream>
#include <map>
using namespace std ;
#ifdef DeBUG
#define bug assert
#else
#define bug //
#endif
#define zero {0}
#define INF 2000000000
#define EPS 1e-10
inline int sgn(double x)//sgn函数符号判断 ，小于给定精度判零
{
return fabs(x) < EPS ? 0 :(x < 0 ? -1 : 1);
}
struct POINT
{
double x;
double y;
POINT()
{
}
POINT(double a,double b):x(a),y(b)
{
}
};
double dist(POINT p,POINT r)
{
return sqrt((p.x-r.x)*(p.x-r.x)+(p.y-r.y)*(p.y-r.y));
}
bool cocircle(POINT p1,POINT p2,POINT p3,POINT &q,double &r)
{
double x12=p2.x-p1.x;
double y12=p2.y-p1.y;
double x13=p3.x-p1.x;
double y13=p3.y-p1.y;
double z2=x12*(p1.x+p2.x)+y12*(p1.y+p2.y);
double z3=x13*(p1.x+p3.x)+y13*(p1.y+p3.y);
double d=2.0*(x12*(p3.y-p2.y)-y12*(p3.x-p2.x));
if(abs(d)<EPS)                           //共线，圆不存在
return false;
q.x=(y13*z2-y12*z3)/d;
q.y=(x12*z3-x13*z2)/d;
r=dist(p1,q);
return true;
}
int main()
{
#ifdef DeBUGn

freopen("C:\\Users\\Sky\\Desktop\\1.in","r",stdin);
#endif
int T;
double x1,x2,x3,y1,y2,y3;
scanf("%d",&T);
while(T--)
{
POINT xin;
double r;
cin>>x1>>y1>>x2>>y2>>x3>>y3;
/*
if(sgn((x3-x1)*(y2-y1)-(y3-y1)*(x2-x1))==0)
printf("No this position\n");
else
{*/
if(cocircle(POINT(x1,y1),POINT(x2,y2),POINT(x3,y3),xin,r))
printf("%.1lf %.1lf\n",xin.x,xin.y);
else if((x1==x2&&y1==y2)||(x1==x3&&y1==y3)||(x2==x3&&y2==y3))//知道数据了这里偷个懒呵呵，应判断两点中点
printf("%.1lf %.1lf\n",(x1+x2+x3)/2,(y1+y2+y3)/2);
else
printf("No this position\n");
//}
}
return 0;
}

1. 这道题目的核心一句话是：取还是不取。
如果当前取，则index+1作为参数。如果当前不取，则任用index作为参数。

2. 第一题是不是可以这样想，生了n孩子的家庭等价于n个家庭各生了一个1个孩子，这样最后男女的比例还是1:1

3. #!/usr/bin/env python
def cou(n):
arr =
i = 1
while(i<n):
arr.append(arr[i-1]+selfcount(i))
i+=1
return arr[n-1]

def selfcount(n):
count = 0
while(n):
if n%10 == 1:
count += 1
n /= 10
return count

4. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮