HDU 4666 Hyperspace
曼哈顿距离：|x1-x2|+|y1-y2|。
最远曼哈顿距离，枚举x1与x2的关系以及y1与y2的关系，取最大值就是答案。
#include<cstdio>
#include<set>
#define oo 0x7FFFFFFF
#define MAXM 35
#define MAXN 100010
using namespace std;
multiset<int> myset[MAXM];
struct Ask {
int cmd;
int arr[MAXM];
} q[MAXN];
int main() {
int n, m;
int i, j, k;
int tmp;
int res;
int ans;
multiset<int>::iterator it1, it2;
while (~scanf("%d%d", &n, &m)) {
for (i = ; i < MAXM; i++) {
myset[i].clear();
}
for (i = ; i <= n; i++) {
scanf("%d", &q[i].cmd);
if (q[i].cmd == ) {
for (j = ; j < m; j++) {
scanf("%d", &q[i].arr[j]);
}
} else {
scanf("%d", &tmp);
q[i].cmd = q[tmp].cmd ^ ;
for (j = ; j < m; j++) {
q[i].arr[j] = q[tmp].arr[j];
}
}
}
for (i = ; i <= n; i++) {
if (q[i].cmd == ) {
for (j = ; j < ( << m); j++) {
tmp = j;
res = ;
for (k = ; k < m; tmp >>= , k++) {
if (tmp & ) {
res -= q[i].arr[k];
} else {
res += q[i].arr[k];
}
}
myset[j].insert(res);
}
} else {
for (j = ; j < ( << m); j++) {
tmp = j;
res = ;
for (k = ; k < m; tmp >>= , k++) {
if (tmp & ) {
res -= q[i].arr[k];
} else {
res += q[i].arr[k];
}
}
myset[j].erase(myset[j].find(res));
}
}
ans = -oo;
for (j = ; j < ( << m); j++) {
if (myset[j].size() > ) {
break;
}
}
if (j >= ( << m)) {
ans = ;
} else {
for (j = ; j < ( << m); j++) {
if (myset[j].size() > ) {
it1 = myset[j].end();
it1--;
it2 = myset[j].begin();
ans = max(ans, (*it1 - *it2));
}
}
}
printf("%d\n", ans);
}
}
return ;
}
HDU 4667 Building Fence
三角形上的点当作普通点。
点与圆的切点可能是凸包上的点。
两圆公切线与圆的交点也可能是凸包上的点。
凸包上两个点属于同一个圆，则长度等于弧长。否则长度就是线段距离。
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#define MAXN 500010
#define EPS 1e-8
const double PI = acos(-1.0);
using namespace std;
struct Point {
double x, y;
int idx;
Point(double _x = , double _y = , int _idx = ) {
x = _x;
y = _y;
idx = _idx;
}
};
struct Circle {
Point o;
double r;
};
vector<Point> p;
Point st[MAXN];
int top;
Circle c[MAXN];
inline int dbcmp(double x, double y) {
if (fabs(x - y) < EPS) {
return ;
} else {
return x > y ? : -;
}
}
bool cmp(Point p1, Point p2) {
if (dbcmp(p1.y, p2.y)) {
return p1.y < p2.y;
} else {
return p1.x < p2.x;
}
}
Point operator+(Point p1, Point p2) {
return Point(p1.x + p2.x, p1.y + p2.y);
}
Point operator-(Point p1, Point p2) {
return Point(p1.x - p2.x, p1.y - p2.y);
}
Point operator*(Point p1, double k) {
return Point(p1.x * k, p1.y * k);
}
Point Rotate(Point p, double angle) {
Point res;
res.x = p.x * cos(angle) - p.y * sin(angle);
res.y = p.x * sin(angle) + p.y * cos(angle);
return res;
}
void TangentPoint_PC(Point poi, Point o, double r, Point &result1,
Point &result2) {
double line = sqrt(
(poi.x - o.x) * (poi.x - o.x) + (poi.y - o.y) * (poi.y - o.y));
double angle = acos(r / line);
Point unitvector, lin;
lin.x = poi.x - o.x;
lin.y = poi.y - o.y;
unitvector.x = lin.x / sqrt(lin.x * lin.x + lin.y * lin.y) * r;
unitvector.y = lin.y / sqrt(lin.x * lin.x + lin.y * lin.y) * r;
result1 = Rotate(unitvector, -angle);
result2 = Rotate(unitvector, angle);
result1.x += o.x;
result1.y += o.y;
result2.x += o.x;
result2.y += o.y;
return;
}
inline double dist(Point p1, Point p2) {
return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
void TangentPoint_CC(Circle c1, Circle c2) {
if (dbcmp(c1.r, c2.r) > ) {
swap(c1, c2);
}
double c2c = dist(c1.o, c2.o);
double height = c2.r - c1.r;
double alpha = asin(height / c2c) + PI / ;
Point v1, v2, tmp;
v1 = c2.o - c1.o;
double len = dist(v1, Point(, ));
v1.x /= len;
v1.y /= len; v2 = Rotate(v1, alpha);
tmp = v2 * c1.r + c1.o;
tmp.idx = c1.o.idx;
p.push_back(tmp);
tmp = v2 * c2.r + c2.o;
tmp.idx = c2.o.idx;
p.push_back(tmp); v2 = Rotate(v1, -alpha);
tmp = v2 * c1.r + c1.o;
tmp.idx = c1.o.idx;
p.push_back(tmp);
tmp = v2 * c2.r + c2.o;
tmp.idx = c2.o.idx;
p.push_back(tmp);
}
inline double xmult(Point p0, Point p1, Point p2) {
return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}
double dot(Point a, Point b) {
return a.x * b.x + a.y * b.y;
}
double cross(Point a, Point b) {
return a.x * b.y - a.y * b.x;
}
double len(Point a) {
return sqrt(a.x * a.x + a.y * a.y);
}
double angle(Point a, Point b) {
double ret = acos(dot(a, b) / (len(a) * len(b)));
if (cross(a, b) > ) {
return ret;
} else {
return * PI - ret;
}
}
int main() {
int n, m;
int i, j;
double x, y;
int tmp;
Point p1, p2;
double ans;
while (~scanf("%d%d", &n, &m)) {
p.clear();
for (i = ; i < n; i++) {
scanf("%lf%lf%lf", &x, &y, &c[i].r);
c[i].o = Point(x, y, i);
}
for (i = ; i < m; i++) {
for (j = ; j < ; j++) {
scanf("%lf%lf", &x, &y);
p.push_back(Point(x, y, -));
}
}
for (i = ; i < n; i++) {
for (j = ; j < * m; j++) {
TangentPoint_PC(p[j], c[i].o, c[i].r, p1, p2);
p1.idx = p2.idx = c[i].o.idx;
p.push_back(p1);
p.push_back(p2);
}
}
for (i = ; i < n; i++) {
for (j = i + ; j < n; j++) {
TangentPoint_CC(c[i], c[j]);
}
}
sort(p.begin(), p.end(), cmp);
top = -;
for (i = ; i < (int) p.size(); i++) {
while (top > && dbcmp(xmult(st[top - ], st[top], p[i]), ) <= ) {
top--;
}
st[++top] = p[i];
}
tmp = top;
for (i = p.size() - ; i >= ; i--) {
while (top > tmp && dbcmp(xmult(st[top - ], st[top], p[i]), ) <= ) {
top--;
}
st[++top] = p[i];
}
if (n == && m == ) {
ans = * PI * c[].r;
} else {
ans = ;
for (i = ; i < top; i++) {
if (st[i].idx < || st[i + ].idx <
|| st[i].idx != st[i + ].idx) {
ans += dist(st[i], st[i + ]);
} else {
ans += c[st[i].idx].r
* angle(st[i] - c[st[i].idx].o,
st[i + ] - c[st[i].idx].o);
}
}
}
printf("%.5lf\n", ans);
}
return ;
}