Luogu P1381油滴扩展

传送门

数据范围给的很小啊，n >= 0 && n <= 7，所以给了DFS生存的空间。

对于每一个油滴，可以说在它下一个油滴放置之前，当前的这个油滴的半径并不确定（但是对于边界情况是可以判断的）。

当把下一个油滴滴入时，当前油滴的半径就已经确定了（如果这个油滴滴在上一个油滴的范围内，就直接return 0，避免冗余计算）。

注意：在DFS中每次的r[j]和v[j]都要重置为0（血的教训）。

CODE:

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 #include <cctype>

 #include <queue>

 #include <cmath>

 #define zxy(i,a,b) for(int i = a ; i <= b ; i++)

 #define zxyzxy(i,a,b) for(int i = a ; i < b ; i++)

 #define yxz(i,a,b) for(int i = a ; i >= b ; i--)

 #define yxzyxz(i,a,b) for(int i = a ; i > b ; i--)

 #define gameover printf("\n")

 #define N 1000005

 #define mod 100003

 #define INF 0x7fffffff

 #define PI 3.14159265358979323846

 #define y1 y111111111111

 #define bin return

 typedef long long ll;

 typedef double db;

 typedef float fl;

 typedef char cr;

 using namespace std;

 int read()

 {

     int x = ,t = ;

     char c = getchar();

     while((c > '' || c < '') && c != '-')

         c = getchar();

     if(c == '-')

         t = -,c = getchar();

     while(c >= '' && c <= '')

         x = x *  + c - ,c = getchar();

     bin x * t;

 }

 void write(ll x)

 {

     if(x < )

         x = -x,putchar('-');

     if(x >= )

         write(x / );

     putchar(x %  + '');

 }

 int n;

 int x2,y2,x1,y1;

 int x[N],y[N];

 int v[N];

 db o = -,r[N];

 int quick_pow(int a,int b)

 {

     int base = a,ans = ;

     while(b)

     {

         if(b & )

             ans = ans * base;

         base = base * base;

         b>>=;

     }

     bin ans;

 }

 db mymin(db a,db b)

 {

     if(a > b)

         return b;

     bin a;

 }

 db mymax(db a,db b)

 {

     if(a > b)

         return a;

     bin b;

 }

 db dis(int xx,int yy,int xxx,int yyy)

 {

     bin sqrt(quick_pow((abs(xx - xxx)),) + quick_pow((abs(yy - yyy)),));

 }

 db work(int i)

 {

     zxy(j,,n)

     if(j != i && v[j])

         if(r[j] > dis(x[j],y[j],x[i],y[i]))

             return ;

     db lr = min(abs(x[i] - x2),abs(x[i] - x1));

     db hb = min(abs(y[i] - y2),abs(y[i] - y1));

     db ans = mymin(lr,hb);

     db distance;

     zxy(j,,n)

     if(j != i && v[j])

     {

         distance = dis(x[j],y[j],x[i],y[i]) - r[j];

         ans = min(ans,distance);

     }

     bin ans;

 }

 void DFS(int i,db step)

 {

     if(i > n)

     {

         o = mymax(o,step);

         bin;

     }

     zxy(j,,n)

     {

         if(!r[j])

         {

             r[j] = work(j);

             v[j] = ;

             DFS(i + ,step + PI * r[j] * r[j]);

             v[j] = ;

         r[j] = ;

         }

     }

 }

 int main()

 {

     n = read();

     x2 = read(),y2 = read(),x1 = read(),y1 = read();

     db s = abs(x2 - x1) * abs(y2 - y1);

     zxy(i,,n)

         x[i] = read(),y[i] = read();

     DFS(,);

 //    cout<<o<<endl;

     printf("%.0lf\n",s - o);

     gameover;

     bin ;

 }

 /*

 3

 -98 5 30 30

 -42 11

 -51 17

 -11 22

 */