SRM465

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  * sqrt(x * x + y * y);

        }

        long long count(vector <int> x, vector <int> y)

        {

              long long ans = ;

              int n = x.size();

              long long d;

              for (int i = ; i < n; ++i)

                 for (int j = i + ; j < n; ++j){

                     d = floor(dist(x[i], y[i], x[j], y[j]) + eps);

                     ans += (d - ) * d / ;

                 }

              return ans;

        }

};

500pt:

给定最多50个炮台， 50个基地，50个供电厂的位置，并且每个炮台攻击范围为L，而对于每个基地，摧毁它或者摧毁他的供电设施会使他无法工作，求使这些基地都无法工作最少需要的能量为多少（攻击一次能量消耗为距离的平方和）

思路：对于每个基地，摧毁它显然要选择能量最少的炮台，供电厂也同样。那么其实就是一个最小割模型。

对于S，对每个基地i建一条流量为摧毁它能量大小的边

对于T，建一条供电厂j到T，流量为摧毁它能量大小的边

对于基地i与供电厂j，如果供电厂j给基地供电，建i->j,流量为Inf的边，

最后跑一边最大流即可

 // BEGIN CUT HERE

 /*

 */

 // END CUT HERE

 #line 7 "GreenWarfare.cpp"

 #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 M0(a) memset(a, 0, sizeof(a))

 #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 maxn 1200

 #define Inf 0x3fffffff

 #define maxm 210000

 typedef vector<int> VI;

 typedef vector<string> VS;

 typedef vector<double> VD;

 typedef long long LL;

 typedef pair<int,int> PII;

 struct oo{

       int y, next, f;

 };

 struct MaxFlow{

        int n, S, T, tot;

        int son[maxn], dist[maxn], gap[maxn];

        oo e[maxm];

        int sap(int x, int aug){

            if (x == T) return aug;

            int mind = n, sum = ;

            int y, f;

            for (int p = son[x]; p != -; p = e[p].next){

                   y = e[p].y;

                   if (dist[y] +  == dist[x] && e[p].f){

                        f = sap(y, min(e[p].f, aug - sum));

                        e[p].f -= f;

                        e[p^].f += f;

                        sum += f;

                        if (sum == aug || dist[S] >= n) return sum;

                   }

                   if (e[p].f) mind = min(mind, dist[y]);

            }

            if (!sum){

                if (!(--gap[dist[x]])) dist[S] = n;

                ++gap[dist[x] = mind + ];

            }

            return sum;

        }

        void add_edge(int x, int y, int f){

             e[tot].y = y; e[tot].f = f;

             e[tot].next = son[x]; son[x] = tot++;

             e[tot].y = x; e[tot].f = ;

             e[tot].next = son[y]; son[y] = tot++;

        }

        void init(int S, int T, int n){

             memset(son, -, sizeof(son));

             tot = ;

             this->S = S, this->T = T, this->n = n;

        }

        int maxflow(){

             M0(gap);

             M0(dist);

             gap[] = n;

             int ans = ;

             while (dist[S] < n) ans += sap(S, Inf);

             return ans;

        }

 } F;

 class GreenWarfare

 {

         public:

         int n, m, k;

         int dist(int x1, int y1, int x2, int y2){

              int x = x1 - x2;

              int y = y1 - y2;

              return x * x + y * y;

         }

         int minimumEnergyCost(vector <int> cX, vector <int> cY, vector <int> bX, vector <int> bY, vector <int> pX, vector <int> pY, int SPL)

         {

                 n = cX.size(), m = bY.size(), k = pX.size();

                 F.init(, m + k + , m + k + );

                 //printf("%d %d\n", F.T, F.n);

                 for (int i = ; i < m; ++i)

                    for (int j = ; j < k; ++j)

                        if (dist(bX[i], bY[i], pX[j], pY[j]) <= SPL * SPL) F.add_edge(i + , m + j + , Inf);

                 for (int i = ; i < m; ++i){

                     int d = Inf;

                     for (int j = ; j < n; ++j)

                         d = min(d, dist(bX[i], bY[i], cX[j], cY[j]));

                     F.add_edge(, i + , d);

                 }

                 for (int i = ; i < k; ++i){

                     int d = Inf;

                     for (int j = ; j < n; ++j)

                         d = min(d, dist(pX[i], pY[i], cX[j], cY[j]));

                     F.add_edge(i +  + m, F.T, d);

                 }

              //   for (int i = 0; i < F.tot; ++i)

                //     printf("%d %d %d\n",F.e[i].y, F.e[i].f, F.e[i].next);

                 return F.maxflow();

         }

 };