NC16845. Connecting segments
描述
Niuniu has N directed segments. Each segment has one color. He wants to make a powerful sword by connecting the segments. He can choose at most K segments. He isn’t allowed to choose more than one segment from each color, or rotate segments. The powerfulness of the sword is calculated by the square of the distance between the beginning of the first segment and the end of the last segment. Niuniu wants to know the largest powerfulness when K = 1,…, N.
输入描述
The input has the format as described below.
N
x1 y1 c1
x2 y2 c2
...
xn yn cnN is the number of segments. (1 ≤ N ≤ 1000) The ith segment starts at (0,0), ends at(xi,yi), with color ci. (-1000000 ≤ xi,yi ≤ 1000000, xi2+yi2>0, 1 ≤ ci ≤ n)
输出描述
You should output the answers in one line, separated by a space.
示例1
输入:
4 1 2 1 2 1 1 2 3 2 3 1 2
输出:
13 34 34 34
示例2
输入:
2 1 1 1 -1 -1 2
输出:
2 2
示例3
输入:
10 1 4 1 -2 3 2 3 2 1 2 5 3 -4 2 3 -3 3 1 3 1 2 -10 -10 4 7 7 4 7 7 5
输出:
200 392 617 818 976 976 976 976 976 976
C++14(g++5.4) 解法, 执行用时: 1446ms, 内存消耗: 640K, 提交时间: 2019-03-02 22:28:19
#include <bits/stdc++.h>
using LL = long long;
const int max_N = 1000 + 21;
struct P {
int x, y;
explicit P(int x = 0, int y = 0) : x(x), y(y) {}
inline P add(const P &p) const { return P(x + p.x, y + p.y); }
inline P sub(const P &p) const { return P(x - p.x, y - p.y); }
inline LL dot(const P &p) const { return 1ll * x * p.x + 1ll * y * p.y; }
inline LL det(const P &p) const { return 1ll * x * p.y - 1ll * y * p.x; }
inline LL abs2() { return dot(*this); }
inline bool operator==(const P &p) { return x == p.x && y == p.y; }
} p[max_N], s[max_N], cur;
int n, c[max_N], Q[max_N], rk[max_N];
LL ans[max_N];
bool fir[max_N], vis[max_N];
struct functor {
bool operator()(int a, int b) {
P x = p[Q[a + 1]].sub(p[Q[a]]);
P y = p[Q[b + 1]].sub(p[Q[b]]);
LL det = x.det(y);
if (det) return det > 0;
if (x.dot(y) < 0) return cur.dot(x) > 0;
return a < b;
}
};
std::set<int, functor> set;
void updt(int i) {
s[i] = s[i - 1];
rk[i] = rk[i - 1];
int x = Q[i];
if (fir[x]) {
s[i] = s[i].add(p[x]);
++rk[i];
ans[rk[i]] = std::max(ans[rk[i]], s[i].abs2());
}
}
void maintain(int i, bool tp) {
if (!i || i >= n) return;
if (p[Q[i]] == p[Q[i + 1]]) return;
if (tp) set.insert(i);
else set.erase(i);
}
void swap(int i) {
maintain(i - 1, false);
maintain(i, false);
maintain(i + 1, false);
std::swap(Q[i], Q[i + 1]);
if (c[Q[i]] == c[Q[i + 1]] && (fir[Q[i]] || fir[Q[i + 1]])) {
std::swap(fir[Q[i]], fir[Q[i + 1]]);
for (int j = i; j <= n; ++j) updt(j);
} else {
updt(i), updt(i + 1);
}
maintain(i - 1, true);
maintain(i, true);
maintain(i + 1, true);
}
void solve() {
for (int i = 1; i <= n; ++i) Q[i] = i;
std::sort(Q + 1, Q + 1 + n, [&](int a, int b) {
return p[a].y == p[b].y ? p[a].x < p[b].x : p[a].y < p[b].y;
});
cur = P(1, 0);
for (int i = 1; i <= n; ++i) {
if (!vis[c[Q[i]]]) vis[c[Q[i]]] = fir[Q[i]] = true;
updt(i);
maintain(i, true);
}
P st = cur, pre = cur;
while (!set.empty()) {
int x = *set.begin();
set.erase(set.begin());
cur = p[Q[x + 1]].sub(p[Q[x]]);
if ((pre.det(st) > 0 || (!pre.det(st) && pre.dot(st) < 0)) &&
(st.det(cur) > 0 || (!st.det(cur) && st.dot(cur) > 0)))
break;
swap(x);
pre = cur;
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d%d%d", &p[i].x, &p[i].y, c + i);
}
solve();
for (int i = 1; i <= n; ++i) {
ans[i] = std::max(ans[i], ans[i - 1]);
printf("%lld%c", ans[i], " \n"[i == n]);
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 1986ms, 内存消耗: 608K, 提交时间: 2018-08-28 15:49:29
#include <bits/stdc++.h>
using LL = long long;
const int max_N = 1000 + 21;
struct P {
int x, y;
explicit P(int x = 0, int y = 0) : x(x), y(y) {}
inline P add(const P &p) const { return P(x + p.x, y + p.y); }
inline P sub(const P &p) const { return P(x - p.x, y - p.y); }
inline LL dot(const P &p) const { return 1ll * x * p.x + 1ll * y * p.y; }
inline LL det(const P &p) const { return 1ll * x * p.y - 1ll * y * p.x; }
inline LL abs2() { return dot(*this); }
inline bool operator==(const P &p) { return x == p.x && y == p.y; }
} p[max_N], s[max_N], cur;
int n, c[max_N], Q[max_N], rk[max_N];
LL ans[max_N];
bool fir[max_N], vis[max_N];
struct functor {
bool operator()(int a, int b) {
P x = p[Q[a + 1]].sub(p[Q[a]]), y = p[Q[b + 1]].sub(p[Q[b]]);
LL det = x.det(y);
if (det) return det > 0;
if (!cur.det(y) && x.dot(y) < 0) return cur.dot(x) > 0;
return a < b;
}
};
std::set<int, functor> set;
void updt(int i) {
s[i] = s[i - 1];
rk[i] = rk[i - 1];
int x = Q[i];
if (fir[x]) {
s[i] = s[i].add(p[x]);
++rk[i];
ans[rk[i]] = std::max(ans[rk[i]], s[i].abs2());
}
}
void maintain(int i, bool tp) {
if (!i || i >= n) return;
if (p[Q[i]] == p[Q[i + 1]]) return;
if (tp) set.insert(i);
else set.erase(i);
}
void swap(int i) {
maintain(i - 1, false);
maintain(i, false);
maintain(i + 1, false);
std::swap(Q[i], Q[i + 1]);
if (c[Q[i]] == c[Q[i + 1]] && (fir[Q[i]] || fir[Q[i + 1]])) {
std::swap(fir[Q[i]], fir[Q[i + 1]]);
for (int j = i; j <= n; ++j) updt(j);
} else {
updt(i), updt(i + 1);
}
maintain(i - 1, true);
maintain(i, true);
maintain(i + 1, true);
}
void solve() {
for (int i = 1; i <= n; ++i) Q[i] = i;
std::sort(Q + 1, Q + 1 + n, [&](int a, int b) {
return p[a].y == p[b].y ? p[a].x < p[b].x : p[a].y < p[b].y;
});
cur = P(1, 0);
for (int i = 1; i <= n; ++i) {
if (!vis[c[Q[i]]]) vis[c[Q[i]]] = fir[Q[i]] = true;
updt(i);
maintain(i, true);
}
P st = cur, pre = cur;
while (!set.empty()) {
int x = *set.begin();
set.erase(x);
cur = p[Q[x + 1]].sub(p[Q[x]]);
if ((pre.det(st) > 0 || (!pre.det(st) && pre.dot(st) < 0)) && (st.det(cur) > 0 || (!st.det(cur) && st.dot(cur) > 0))) break;
swap(x);
pre = cur;
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d%d%d", &p[i].x, &p[i].y, c + i);
}
solve();
for (int i = 1; i <= n; ++i) {
ans[i] = std::max(ans[i], ans[i - 1]);
printf("%lld%c", ans[i], " \n"[i == n]);
}
return 0;
}