250pt:
给定50个整数点，范围-500-500之间。然后在这些点上选2个点作为中心，画边长为整数的正方形，并且正方形不能重叠（可以不平行），而且而且边长不同为不同方案。求有多少种方案。。
思路：枚举两个点，计算两点的方案数。
#include <cstdlib> #include <cctype> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <string> #include <iostream> #include <sstream> #include <map> #include <set> #include <queue> #include <stack> #include <fstream> #include <numeric> #include <iomanip> #include <bitset> #include <list> #include <stdexcept> #include <functional> #include <utility> #include <ctime> using namespace std; #define PB push_back #define MP make_pair #define REP(i,n) for(i=0;i<(n);++i) #define FOR(i,l,h) for(i=(l);i<=(h);++i) #define FORD(i,h,l) for(i=(h);i>=(l);--i) #define eps 1e-8 typedef vector<int> VI; typedef vector<string> VS; typedef vector<double> VD; typedef long long LL; typedef pair<int,int> PII; class TurretPlacement { public: double dist(int x1, int y1, int x2, int y2){ double x = x1 - x2; double y = y1 - y2; return 2 * sqrt(x * x + y * y); } long long count(vector <int> x, vector <int> y) { long long ans = 0; int n = x.size(); long long d; for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j){ d = floor(dist(x[i], y[i], x[j], y[j]) + eps); ans += (d - 1) * d / 2; } return ans; } };
500pt:
给定最多50个炮台， 50个基地，50个供电厂的位置，并且每个炮台攻击范围为L，而对于每个基地，摧毁它或者摧毁他的供电设施会使他无法工作，求使这些基地都无法工作最少需要的能量为多少（攻击一次能量消耗为距离的平方和）
思路：对于每个基地，摧毁它显然要选择能量最少的炮台，供电厂也同样。那么其实就是一个最小割模型。
对于S，对每个基地i建一条流量为摧毁它能量大小的边
对于T，建一条供电厂j到T，流量为摧毁它能量大小的边
对于基地i与供电厂j，如果供电厂j给基地供电，建i->j,流量为Inf的边，
最后跑一边最大流即可
1 // BEGIN CUT HERE 2 /* 3 4 */ 5 // END CUT HERE 6 #line 7 "GreenWarfare.cpp" 7 #include <cstdlib> 8 #include <cctype> 9 #include <cstring> 10 #include <cstdio> 11 #include <cmath> 12 #include <algorithm> 13 #include <vector> 14 #include <string> 15 #include <iostream> 16 #include <sstream> 17 #include <map> 18 #include <set> 19 #include <queue> 20 #include <stack> 21 #include <fstream> 22 #include <numeric> 23 #include <iomanip> 24 #include <bitset> 25 #include <list> 26 #include <stdexcept> 27 #include <functional> 28 #include <utility> 29 #include <ctime> 30 using namespace std; 31 32 #define PB push_back 33 #define MP make_pair 34 #define M0(a) memset(a, 0, sizeof(a)) 35 #define REP(i,n) for(i=0;i<(n);++i) 36 #define FOR(i,l,h) for(i=(l);i<=(h);++i) 37 #define FORD(i,h,l) for(i=(h);i>=(l);--i) 38 #define maxn 1200 39 #define Inf 0x3fffffff 40 #define maxm 210000 41 typedef vector<int> VI; 42 typedef vector<string> VS; 43 typedef vector<double> VD; 44 typedef long long LL; 45 typedef pair<int,int> PII; 46 struct oo{ 47 int y, next, f; 48 }; 49 struct MaxFlow{ 50 int n, S, T, tot; 51 int son[maxn], dist[maxn], gap[maxn]; 52 oo e[maxm]; 53 54 int sap(int x, int aug){ 55 if (x == T) return aug; 56 int mind = n, sum = 0; 57 int y, f; 58 for (int p = son[x]; p != -1; p = e[p].next){ 59 y = e[p].y; 60 if (dist[y] + 1 == dist[x] && e[p].f){ 61 f = sap(y, min(e[p].f, aug - sum)); 62 e[p].f -= f; 63 e[p^1].f += f; 64 sum += f; 65 if (sum == aug || dist[S] >= n) return sum; 66 } 67 if (e[p].f) mind = min(mind, dist[y]); 68 } 69 if (!sum){ 70 if (!(--gap[dist[x]])) dist[S] = n; 71 ++gap[dist[x] = mind + 1]; 72 } 73 return sum; 74 } 75 76 void add_edge(int x, int y, int f){ 77 e[tot].y = y; e[tot].f = f; 78 e[tot].next = son[x]; son[x] = tot++; 79 e[tot].y = x; e[tot].f = 0; 80 e[tot].next = son[y]; son[y] = tot++; 81 } 82 83 void init(int S, int T, int n){ 84 memset(son, -1, sizeof(son)); 85 tot = 0; 86 this->S = S, this->T = T, this->n = n; 87 } 88 int maxflow(){ 89 M0(gap); 90 M0(dist); 91 gap[0] = n; 92 int ans = 0; 93 while (dist[S] < n) ans += sap(S, Inf); 94 return ans; 95 } 96 } F; 97 98 class GreenWarfare 99 { 100 public: 101 int n, m, k; 102 int dist(int x1, int y1, int x2, int y2){ 103 int x = x1 - x2; 104 int y = y1 - y2; 105 return x * x + y * y; 106 } 107 int minimumEnergyCost(vector <int> cX, vector <int> cY, vector <int> bX, vector <int> bY, vector <int> pX, vector <int> pY, int SPL) 108 { 109 n = cX.size(), m = bY.size(), k = pX.size(); 110 F.init(0, m + k + 1, m + k + 2); 111 //printf("%d %d ", F.T, F.n); 112 for (int i = 0; i < m; ++i) 113 for (int j = 0; j < k; ++j) 114 if (dist(bX[i], bY[i], pX[j], pY[j]) <= SPL * SPL) F.add_edge(i + 1, m + j + 1, Inf); 115 for (int i = 0; i < m; ++i){ 116 int d = Inf; 117 for (int j = 0; j < n; ++j) 118 d = min(d, dist(bX[i], bY[i], cX[j], cY[j])); 119 F.add_edge(0, i + 1, d); 120 } 121 for (int i = 0; i < k; ++i){ 122 int d = Inf; 123 for (int j = 0; j < n; ++j) 124 d = min(d, dist(pX[i], pY[i], cX[j], cY[j])); 125 F.add_edge(i + 1 + m, F.T, d); 126 } 127 // for (int i = 0; i < F.tot; ++i) 128 // printf("%d %d %d ",F.e[i].y, F.e[i].f, F.e[i].next); 129 return F.maxflow(); 130 } 131 132 };