greg666

greg666
12天前

greg666
20天前

greg666
2个月前
Hello, world.

greg666
2个月前

const double eps = 1e-9;
vector<vector<double>> getCenters(vector<int> p1, vector<int> p2, int r) {
double x1 = p1[0], y1 = p1[1];
double x2 = p2[0], y2 = p2[1];
double xc = (x1 + x2) / 2;
double yc = (y1 + y2) / 2;
double d = sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
if (d / 2 >  r + eps) {
return {};
}

vector<double> v = {(x2 - x1) / d, (y2 - y1) / d};
/*
cos, -sin  --> 0, -1  -->  0, 1
sin,  cos      1,  0      -1, 0

(x, y) -> (y, -x) and (-y, x)
*/
double h = sqrt(r * r - (d / 2) * (d / 2));

vector<vector<double>> res;
res.push_back({xc + v[1] * h, yc - v[0] * h});
res.push_back({xc - v[1] * h, yc + v[0] * h});
return res;
}

int numPoints(vector<vector<int>>& points, int r) {
int n = points.size();
int res = 1;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
vector<vector<double>> centers = getCenters(points[i], points[j], r);
for (auto center : centers) {
int cnt = 0;
double cx = center[0];
double cy = center[1];
for (int k = 0; k < n; k++) {
double x = points[k][0];
double y = points[k][1];
if ((cx - x) * (cx - x) + (cy - y) * (cy - y) < r * r + eps) {
cnt++;
}
}
res = max(res, cnt);
}
}
}
return res;
}


greg666
5个月前
// 捉迷藏
const int N = 200, M = 30000;
bool d[N + 1][N + 1];
bool st[N + 1];
int match[N + 1];

bool find(int u, int n) {
for (int v = 1; v <= n; v++) {
if (!d[u][v]) {
continue;
}

if (st[v]) {
continue;
}
st[v] = true;

int t = match[v];
if (t == 0 || find(t, n)) {
match[v] = u;
return true;
}
}

return false;
}

int solve(int n) {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
d[i][j] |= d[i][k] & d[k][j];
}
}
}

int res = 0;
for (int i = 1; i <= n; i++) {
memset(st, 0, sizeof st);
if (find(i, n)) {
res++;
}
}

return n - res;
}


greg666
5个月前
// 骑士放置
const int N = 100;
PII match[N + 1][N + 1];
bool g[N + 1][N + 1];  // 1-based, 1 is bad block
bool st[N + 1][N + 1];

int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

bool find(int x, int y, int m, int n, int k) {
for (int i = 0; i < 8; i++) {
int a = x + dx[i];
int b = y + dy[i];
if (a < 1 || a > m || b < 1 || b > n) {
continue;
}
if (g[a][b]) {
continue;
}

if (st[a][b]) {
continue;
}
st[a][b] = true;

PII t = match[a][b];
if (t.x == 0 || find(t.x, t.y, m, n, k)) {
match[a][b] = {x, y};
return true;
}
}

return false;
}

int solve(int m, int n, int k) {
int res = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (g[i][j] || (i + j) % 2) {
continue;
}
memset(st, 0, sizeof st);
if (find(i, j, m, n, k)) {
res++;
}
}
}

return m * n - k - res;
}


greg666
5个月前
// 机器任务
const int N = 100, M = 100;
bool g[N][M];  // [0, n - 1], [0, m - 1], but skip 0
int st[M];
int match[M];

bool find(int u, int m) {
for (int v = 0; v < m; v++) {
if (!g[u][v]) {
continue;
}

if (st[v]) {
continue;
}
st[v] = true;

if (match[v] == -1 || find(match[v], m)) {
match[v] = u;
return true;
}
}

return false;
}

int solve(int n, int m) {
int res = 0;
for (int i = 0; i < n; i++) {
memset(st, 0, sizeof st);
if (find(i, m)) {
res++;
}
}
return res;
}


greg666
5个月前
// 棋盘覆盖
const int N = 100;
PII match[N + 1][N + 1];  // 1-based
bool g[N + 1][N + 1];  // bad point true
bool st[N + 1][N + 1];

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

bool find(int x, int y, int n) {
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 1 || nx > n || ny < 1 || ny > n) {
continue;
}
if (g[nx][ny]) {
continue;
}
if (st[nx][ny]) {
continue;
}
st[nx][ny] = true;
PII t = match[nx][ny];
if (t.x == -1 || find(t.x, t.y, n)) {
match[nx][ny] = {x, y};
return true;
}
}

return false;
}

int solve(int n) {
memset(match, -1, sizeof match);

int res = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if ((i + j) % 2 && !g[i][j]) {
memset(st, 0, sizeof st);
if (find(i, j, n)) {
res++;
}
}
}
}

return res;
}


greg666
5个月前
// 关押罪犯
const int N = 2e4, M = 2e5;

int h[N + 1];
int e[M], w[M], ne[M], idx;
int color[N + 1];

void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

bool dfs(int u, int c, int x) {
color[u] = c;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (w[i] <= x) {  // ignore small edges
continue;
}
if (color[v]) {
if (color[v] == c) {
return false;
}
} else if (!dfs(v, 3 - c, x)) {
return false;
}
}

return true;
}

bool check(int n, int x) {
memset(color, 0, sizeof color);
for (int i = 1; i <= n; i++) {
if (!color[i]) {
if (!dfs(i, 1, x)) {
return false;
}
}
}
return true;
}

int solve(int n) {
int l = 0, r = 1e9;
int res = r;
while (l <= r) {
int mid = l + r >> 1;
if (check(n, mid)) {
res = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}

return res;

// while (l < r) {
//     int mid = l + r >> 1;
//     if (check(mid)) {
//         r = mid;
//     } else {
//         l = mid + 1;
//     }
// }
// return r;
}


greg666
5个月前
// 单词游戏
const int N = 26 + 1;
int din[N], dout[N];
int p[N];
bool st[N];

int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}

bool solve() {
int start = 0, end = 0;
for (int i = 0; i < 26; i++) {
if (din[i] != dout[i]) {
if (din[i] == dout[i] + 1) {
end++;
} else if (din[i] + 1 == dout[i]) {
start++;
} else {
return false;
}
}
}

if (!(!start && !end || start == 1 && end == 1)) {
return false;
}

int root = -1;
for (int i = 0; i < 26; i++) {
if (st[i]) {
if (root == -1) {
root = find(i);
} else if (root != find(i)) {
return false;
}
}
}

return true;
}