B Bricks 计算几何乱搞
题意：
给你个立方体，问你能不能放进一个管道里面。
题解：
这是一道非常迷的题，其问题在于，你可以不正着放下去，你需要斜着放。此时你需要枚举你旋转的角度，来判断是否可行。至于枚举的范围和步长，看脸乱搞。
代码：
//#include<iostream> #include<cstring> #include<cmath> #include<algorithm> #include<fstream> using namespace std; long double x[3],y[2]; const long double pi=acos(-1); long double a,b; long double d,e; const long double eps=1e-5; int main() { ifstream cin("bricks.in"); ofstream cout("bricks.out"); cin.sync_with_stdio(false); cin >> x[0] >> x[1] >> x[2] >> y[0] >> y[1]; sort(x, x + 3); sort(y, y + 2); a = x[0], b = x[1]; d = y[0], e = y[1]; if (d - a > -eps && e - b > -eps) { cout << "YES" << endl; return 0; } long double dd = pi / (2 * (3e6)); for (long double t = acos(e / b); t < asin(d / b) + dd; t += dd) { if (min((e - b * cos(t)) / sin(t), (d - b * sin(t)) / cos(t)) > a - eps) { cout << "YES" << endl; return 0; } } cout << "NO" << endl; return 0; }
E Evacuation Plan 最小费用流
题意：
题目好长好长好长。。。。。简单说就是，发生核战争了，人们要避难，给你每个建筑的坐标，给你每个避难所的坐标，每个建筑里面有若干人，从一个建筑到一个避难所的时间，是坐标的曼哈顿距离，现在要你使总时间花费最少。
题解：
就最小费用的模板题。最后在残余网络上寻找解即可。
代码：
//#include <iostream> #include<vector> #include<fstream> #include<cstring> #include<cstdio> #include<queue> #include<algorithm> #include<string> #include<cmath> #define MAX_V 222 #define INF 1008611 using namespace std; struct edge { public: int to, cap, cost, rev; bool isRev; edge(int t, int c, int co, int re,bool ir) : to(t), cap(c), cost(co), rev(re),isRev(ir) { } edge() { } }; int V=0; vector<edge> G[MAX_V]; int dist[MAX_V]; int prevv[MAX_V],preve[MAX_V]; void add_edge(int from,int to,int cap,int cost) { G[from].push_back(edge(to,cap,cost,G[to].size(),0)); G[to].push_back(edge(from,0,-cost,G[from].size()-1,1)); } char cc; int min_cost_flow(int s,int t,int f) { int res = 0; while (f > 0) { fill(dist, dist + V, INF); dist[s] = 0; bool update = 1; while (update) { update = 0; for (int v = 0; v < V; v++) { if (dist[v] == INF)continue; for (int i = 0; i < G[v].size(); i++) { edge &e = G[v][i]; if (e.cap > 0 && dist[e.to] > dist[v] + e.cost) { //cout<<"*"<<endl; dist[e.to] = dist[v] + e.cost; prevv[e.to] = v; preve[e.to] = i; update = 1; } } } } if (dist[t] == INF) return -1; int d = f; for (int v = t; v != s; v = prevv[v]) d = min(d, G[prevv[v]][preve[v]].cap); f -= d; res += d * dist[t]; for (int v = t; v != s; v = prevv[v]) { edge &e = G[prevv[v]][preve[v]]; e.cap -= d; G[v][e.rev].cap += d; } } return res; } int n,m; struct build { public: int x, y,c; build(int xx, int yy,int cc) : x(xx), y(yy), c(cc){ } build() { } int dis(build a){ return abs(a.x-x)+abs(a.y-y)+1; } }; typedef build shelter; build bu[MAX_V]; shelter sh[MAX_V]; int plan; int S=0; int main() { ifstream cin("evacuate.in"); ofstream cout("evacuate.out"); cin.sync_with_stdio(false); cin >> n >> m; for (int i = 0; i < n; i++) { cin >> bu[i].x >> bu[i].y >> bu[i].c; S += bu[i].c; } for (int i = 0; i < m; i++) cin >> sh[i].x >> sh[i].y >> sh[i].c; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { int k; cin >> k; plan += k * bu[i].dis(sh[j]); } for (int i = 0; i < n; i++) add_edge(n + m, i, bu[i].c, 0); for (int j = 0; j < m; j++) add_edge(j + n, n + m + 1, sh[j].c, 0); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) add_edge(i, j + n, INF, bu[i].dis(sh[j])); V = n + m + 2; int tmp = min_cost_flow(n + m, n + m + 1, S); if (tmp == plan) { cout << "OPTIMAL" << endl; return 0; } cout << "SUBOPTIMAL" << endl; for (int i = 0; i < n; i++, cout << endl) for (int j = 0; j < G[i].size(); j++) if (!G[i][j].isRev) cout << INF - G[i][j].cap << " "; return 0; }
I Inlay Cutters 模拟+图论
题意：
给你一个棋盘，现在切若干刀，问你最后有几个三角形。
题解：
由于三个点在平面上只能构成三角形，那么此题可以转化为图论问题来解决，将相邻的直线交点连边，然后在图上求有多少个三元环即可。
代码：
//#include<iostream> #include<fstream> #include<cstring> #include<vector> #include<algorithm> #include<cstdio> #include<string> #include<cmath> #define MAX_N 10004 using namespace std; int N,M,K; int d[4]; struct knife { public: int from, to, dir; knife(int f, int t, int d) : from(f), to(t), dir(d) { } knife() { } }; knife kn[MAX_N]; int cnt[MAX_N]; vector<int> G[MAX_N]; int main() { ifstream cin("inlay.in"); ofstream cout("inlay.out"); cin.sync_with_stdio(false); cin >> M >> N >> K; d[0] = 2 * M + 1; d[1] = 1; d[2] = M + 1; d[3] = M; for (int i = 0; i < K; i++) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; if (y1 > y2 || (y1 == y2 && x1 > x2)) { swap(x1, x2); swap(y1, y2); } int u = x1 * d[1] + y1 * d[0]; int v = x2 * d[1] + y2 * d[0]; int t; if (x1 == x2)t = 0; else if (y1 == y2)t = 1; else if (x2 > x1)t = 2; else t = 3; kn[i] = knife(u, v, t); } kn[K++] = knife(0, M, 1); kn[K++] = knife(N * d[0], N * d[0] + M * d[1], 1); kn[K++] = knife(0, N * d[0], 0); kn[K++] = knife(M, N * d[0] + M, 0); for (int i = 0; i < K; i++) { int u = kn[i].from, v = kn[i].to, t = kn[i].dir; while (u != v) { cnt[u]++; u += d[t]; } cnt[v]++; } int V = -1; for (int i = 0; i < K; i++) { int u = kn[i].from, v = kn[i].to, t = kn[i].dir; int p = u; while (u != v) { u += d[t]; if (cnt[u] > 1) { V = max(V, u); V = max(V, p); G[p].push_back(u); G[u].push_back(p); p = u; } } } int ans = 0; V++; for (int u = 0; u < V; u++) sort(G[u].begin(), G[u].end()); for (int u = 0; u < V; u++) for (auto v:G[u]) for (auto c:G[v]) { if (c == u)continue; int t = lower_bound(G[c].begin(), G[c].end(), u) - G[c].begin(); if (G[c][t] == u)ans++; //cout<<c<<" "<<u<<" "<<v<<endl; } cout << ans/6 << endl; return 0; }