题意：
给出四个点的坐标（每个点的坐标值小于等于1,000,000,000,000），问最后一个点是否在前三个点组成的三角形的外接圆内，是输出Accept，否输出Rejected
解题思路：
题意很好理解，就是判断一个点是否在一个圆内，或者说一个点到圆心的距离是否大于半径，关键是大整数和精度问题，题解中给出了java的解法。
设x0,y0为圆心，有圆心到三个顶点的距离相等，列出如下两个式子：
（x1-x0）*(x1-x0)+(y1-y0)*(y1-y0) = （x2-x0）*(x2-x0)+(y2-y0)*(y2-y0).
（x2-x0）*(x2-x0)+(y2-y0)*(y2-y0) = （x3-x0）*(x3-x0)+(y3-y0)*(y3-y0).
化简可得：
2(x2-x1)x0 + 2(y2-y1)y0 = x2^2 + y2^2 - x1^2 - y1^2.
2(x3-x2)x0 + 2(y3-y2)y0 = x3^2 + y3^2 - x2^2 - y2^2.
令a1 = 2*(x2-x1);
b1 = 2*(y2-y1);
c1 = x2^2 + y2^2 - x1^2 - y1^2;
a2 = 2*(x3-x2);
b2 = 2*(y3-y2);
c2 = x3^2 + y3^2 - x2^2 - y2^2;
则
a1*x0 + b1*y0 = c1;
a2*x0 + b2*y0 = c2;
根据克莱姆法则（具体参见记法2）可得
x0 = (c1*b2 - b1*c2)/(a1*b2 - b1*a2);
y0 = (a1*c2 - c1*a2)/(a1*b2 - b1*a2);
由两点间距离公式得
r = (x1-x0)*(x1-x0)+(y1-y0)*(y1-y0);
d = (x1-x0)*(x1-x0)+(y1-y0)*(y1-y0);(x-x0)*(x-x0)+(y-y0)*(y-y0);(x1-x0)*(x1-x0)+(y1-y0)*(y1-y0);(x1-x0)*(x1-x0)+(y1-y0)*(y1-y0)(x1-x0)*(x1-x0)+(y1-y0)*(y1-y0)
由于涉及到大整数和高精度，使用Java中的BidDecimal代码如下：
import java.math.BigDecimal;
import java.util.Scanner; public class Main { public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
while(T-- > 0) {
BigDecimal x1 = in.nextBigDecimal();
BigDecimal y1 = in.nextBigDecimal();
BigDecimal x2 = in.nextBigDecimal();
BigDecimal y2 = in.nextBigDecimal();
BigDecimal x3 = in.nextBigDecimal();
BigDecimal y3 = in.nextBigDecimal();
BigDecimal x = in.nextBigDecimal();
BigDecimal y = in.nextBigDecimal(); BigDecimal a1 = x2.subtract(x1).multiply(BigDecimal.valueOf(2));
BigDecimal b1 = y2.subtract(y1).multiply(BigDecimal.valueOf(2));
BigDecimal c1 = x2.pow(2).add(y2.pow(2)).subtract(x1.pow(2)).subtract(y1.pow(2)); BigDecimal a2 = x3.subtract(x2).multiply(BigDecimal.valueOf(2));
BigDecimal b2 = y3.subtract(y2).multiply(BigDecimal.valueOf(2));
BigDecimal c2 = x3.pow(2).add(y3.pow(2)).subtract(x2.pow(2)).subtract(y2.pow(2)); BigDecimal x0 = b2.multiply(c1).subtract(b1.multiply(c2)).divide(a1.multiply(b2).subtract(b1.multiply(a2)));
BigDecimal y0 = a1.multiply(c2).subtract(c1.multiply(a2)).divide(a1.multiply(b2).subtract(b1.multiply(a2))); BigDecimal r = x1.subtract(x0).pow(2).add(y1.subtract(y0).pow(2));
BigDecimal d = x.subtract(x0).pow(2).add(y.subtract(y0).pow(2));
if(1 == d.compareTo(r))
System.out.println("Accepted");
else
System.out.println("Rejected");
}
} }
HDU 6208 The Dominator of Strings
题意：
给出n个串，问是否存在一个串能够包含这n个串。
解题思路：
AC自动机的模板题，注意输入字符串的数组开大一点就行了。
#include <cstdio>
#include <cstring> const int K = ;
const int maxn = + ;
struct Node {
Node *ch[K], *fail;
int mc;
void clear(){
memset(this, , sizeof(Node));
}
}; Node *que[maxn*];
struct AC {
Node nodes[maxn], *root, *sroot, *cur;
Node* newNode() {
cur->clear();
return cur++;
}
void clear() {
cur = nodes;
sroot = newNode();
root = newNode();
root->fail = sroot;
for(int i = ; i < K; i++) {
sroot->ch[i] = root;
}
sroot->mc = -;
}
void insert(char *s) {
Node* t = root;
for(; *s; s++) {
int x = *s - 'a';
if(t->ch[x] == NULL)
t->ch[x] = newNode();
t=t->ch[x];
}
t->mc++;
}
void build() {
int p = , q = ;
que[q++] = root;
while(p != q) {
Node *t = que[p++];
for(int i = ; i < K; i++) {
if(t->ch[i]) {
t->ch[i]->fail = t->fail->ch[i];
que[q++] = t->ch[i];
}
else
t->ch[i] = t->fail->ch[i];
}
}
}
int run(char *s) {
int ans = ;
Node* t = root;
for(; *s; s++) {
int x = *s - 'a';
t = t->ch[x];
for(Node* u = t; u->mc != -; u = u->fail) {
ans += u->mc;
u->mc = -;
}
}
return ans;
}
}ac;
int n;
char s[], t[];
int main()
{
int T;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
ac.clear();
int maxl = ;
memset(t, , sizeof(t));
for(int i = ; i < n; i++) {
scanf(" %s", s);
int len = strlen(s);
if(len > maxl) {
maxl = len;
strcpy(t, s);
}
ac.insert(s);
}
ac.build(); if(ac.run(t) == n)
puts(t);
else
puts("No");
}
return ;
}
HDU 6216 A Cubic number and A Cubic Number
题意：
判断一个质数p，是否是两个立方数之差
解题思路：
由题(x^3 - y^3) = p
即(x - y) * (x^2 - 2*x*y + y^2) = p
由于p是质数，所以(x - y) = 1，即x = y + 1，代入原式得
3 * y * y + 3 * y + 1 = p
枚举10^6以内的y，对于每一个p搜索是否存在即可。
#include <cstdio>
typedef long long ll;
const ll maxn = 1e6 + ;
ll ls[maxn]; int main()
{
int T;
ll p;
for(ll i = ; i < maxn; i++) {
ls[i] = * i * i + * i + ;
}
scanf("%d", &T);
while(T--) {
scanf("%lld", &p);
bool f = ;
int le = -, ri = maxn;
while(ri - le > ) {
int mid = (ri + le) >> ;
if(p == ls[mid]) {
f = ;
break;
} else if(p > ls[mid])
le = mid;
else
ri = mid;
}
if(f)
puts("YES");
else
puts("NO");
}
return ;
}
题意：
前提是女的比男的大，给出生肖，问两人的最小年龄差是多少
#include <cstdio>
#include <map>
#include <cstring>
#include <string>
#include <iostream>
using namespace std; const string ls[] = {"rat", "ox", "tiger", "rabbit", "dragon", "snake", "horse", "sheep",
"monkey", "rooster", "dog", "pig"}; int main()
{
int T;
map<string, int> mp;
for(int i = ; i < ; i++) {
mp[ls[i]] = i + ;
}
string a, b;
cin >> T;
while(T--) {
cin >> a >> b;
int c = mp[a];
int d = mp[b];
int ans = d - c; if(ans <= )
ans += ;
cout << ans <<endl;
}
return ;
}