P1378-油滴扩展

柔光的暖阳◎ 2023-06-01 08:47 6阅读 0赞

1 #include <bits/stdc++.h>
     2 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     3 #define _rep(i,a,b) for(int i = (a);i > b;i --)
     4 #define INF 0x3f3f3f3f
     5 #define PI 3.1415926535
     6 typedef long long ll;
     7 using namespace std;
     8 inline ll read()
     9 {
    10     ll ans = 0;
    11     char ch = getchar(), last = ' ';
    12     while(!isdigit(ch)) last = ch, ch = getchar();
    13     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    14     if(last == '-') ans = -ans;
    15     return ans;
    16 }
    17 inline void write(ll x)
    18 {
    19     if(x < 0) x = -x, putchar('-');
    20     if(x >= 10) write(x / 10);
    21     putchar(x % 10 + '0');
    22 }
    23 struct P
    24 {
    25     double x;
    26     double y;
    27 };
    28 double height[2];
    29 double width[2];
    30 int vis[8];
    31 P point[8];
    32 double pointr[8];
    33 int N;
    34 double rnt = 0;
    35 double reach(P p1,P p2)
    36 {
    37     return sqrt(pow(p1.x-p2.x,2)+pow(p1.y-p2.y,2));
    38 }
    39 double findr(int i)
    40 {
    41     double rnt = 10000;
    42 
    43     rnt = min(rnt,min(point[i].x-width[0],width[1]-point[i].x));
    44     rnt = min(rnt,min(point[i].y-height[0],height[1]-point[i].y));
    45     _for(j,0,N)
    46     {
    47         if(i==j)
    48             continue;
    49         if(abs(reach(point[i],point[j])<pointr[j]))
    50             rnt = 0;
    51         if(pointr[j])
    52             rnt = min(rnt,abs(reach(point[i],point[j])-pointr[j]));
    53     }
    54     return rnt;
    55 }
    56 void dfs(int step,double area)
    57 {
    58     if(step==N)
    59         rnt = max(rnt,area);
    60 
    61     _for(i,0,N)
    62     {
    63         if(!vis[i])
    64         {
    65             double r = findr(i);
    66             pointr[i] = r;
    67             vis[i] = 1;
    68             dfs(step+1,area+PI*r*r);
    69             vis[i] = 0;
    70             pointr[i] = 0;
    71         }
    72     }
    73 }
    74 int main()
    75 {
    76     N = read();
    77     width[0] = read(),height[0] = read(),width[1] = read(),height[1] = read();
    78     sort(width,width+2);
    79     sort(height,height+2);
    80     _for(i,0,N)
    81     point[i].x = read(),point[i].y = read();
    82     memset(vis,0,sizeof(vis));
    83     dfs(0,0);
    84 
    85     write((width[1]-width[0])*(height[1]-height[0])-(int)(rnt+0.5));
    86     return 0;
    87 }

转载于:https://www.cnblogs.com/Asurudo/p/11387703.html