题解 P1378 【油滴扩展】
Abx123
·
·
题解
暴力破解
code：
#include <bits/stdc++.h>
using namespace std;
int n, x1, x2, yu, y2, x[7], y[7], max;
double bj1, bj2, bj3, bj4, bj5, bj6, the_max_num;
double max_ab(double x, double y);
double min_ab(double x, double y);
void sc(int q, int q1, int q2, int q3, int q4, int q5, int q6)
{
if (q == 1)
{
bj1 = min_ab(min_ab(fabs(x[q1] - x1), fabs(x[q1] - x2)), min_ab(fabs(y[q1] - yu), fabs(y[q1] - y2)));
the_max_num = max_ab(the_max_num, bj1 * bj1 * 3.1415926);
}
if (q == 2)
{
bj1 = min_ab(min_ab(fabs(x[q1] - x1), fabs(x[q1] - x2)), min_ab(fabs(y[q1] - yu), fabs(y[q1] - y2)));
if (sqrt((x[q2] - x[q1]) * (x[q2] - x[q1]) + (y[q2] - y[q1]) * (y[q2] - y[q1])) <= bj1)
bj2 = 0;
else
bj2 = min_ab(min_ab(min_ab(fabs(x[q2] - x1), fabs(x[q2] - x2)), min_ab(fabs(y[q2] - yu), fabs(y[q2] - y2))), sqrt((x[q2] - x[q1]) * (x[q2] - x[q1]) + (y[q2] - y[q1]) * (y[q2] - y[q1])) - bj1);
the_max_num = max_ab(the_max_num, bj1 * bj1 * 3.1415926 + bj2 * bj2 * 3.1415926);
}
if (q == 3)
{
bj1 = min_ab(min_ab(fabs(x[q1] - x1), fabs(x[q1] - x2)), min_ab(fabs(y[q1] - yu), fabs(y[q1] - y2)));
if (sqrt((x[q2] - x[q1]) * (x[q2] - x[q1]) + (y[q2] - y[q1]) * (y[q2] - y[q1])) <= bj1)
bj2 = 0;
else
bj2 = min_ab(min_ab(min_ab(fabs(x[q2] - x1), fabs(x[q2] - x2)), min_ab(fabs(y[q2] - yu), fabs(y[q2] - y2))), sqrt((x[q2] - x[q1]) * (x[q2] - x[q1]) + (y[q2] - y[q1]) * (y[q2] - y[q1])) - bj1);
if (sqrt((x[q3] - x[q1]) * (x[q3] - x[q1]) + (y[q3] - y[q1]) * (y[q3] - y[q1])) <= bj1 || sqrt((x[q3] - x[q2]) * (x[q3] - x[q2]) + (y[q3] - y[q2]) * (y[q3] - y[q2])) <= bj2)
bj3 = 0;
else
bj3 = min_ab(min_ab(min_ab(min_ab(fabs(x[q3] - x1), fabs(x[q3] - x2)), min_ab(fabs(y[q3] - yu), fabs(y[q3] - y2))), sqrt((x[q3] - x[q1]) * (x[q3] - x[q1]) + (y[q3] - y[q1]) * (y[q3] - y[q1])) - bj1), sqrt((x[q3] - x[q2]) * (x[q3] - x[q2]) + (y[q3] - y[q2]) * (y[q3] - y[q2])) - bj2);
the_max_num = max_ab(the_max_num, bj1 * bj1 * 3.1415926 + bj2 * bj2 * 3.1415926 + bj3 * bj3 * 3.1415926);
}
if (q == 4)
{
bj1 = min_ab(min_ab(fabs(x[q1] - x1), fabs(x[q1] - x2)), min_ab(fabs(y[q1] - yu), fabs(y[q1] - y2)));
if (sqrt((x[q2] - x[q1]) * (x[q2] - x[q1]) + (y[q2] - y[q1]) * (y[q2] - y[q1])) <= bj1)
bj2 = 0;
else
bj2 = min_ab(min_ab(min_ab(fabs(x[q2] - x1), fabs(x[q2] - x2)), min_ab(fabs(y[q2] - yu), fabs(y[q2] - y2))), sqrt((x[q2] - x[q1]) * (x[q2] - x[q1]) + (y[q2] - y[q1]) * (y[q2] - y[q1])) - bj1);
if (sqrt((x[q3] - x[q1]) * (x[q3] - x[q1]) + (y[q3] - y[q1]) * (y[q3] - y[q1])) <= bj1 || sqrt((x[q3] - x[q2]) * (x[q3] - x[q2]) + (y[q3] - y[q2]) * (y[q3] - y[q2])) <= bj2)
bj3 = 0;
else
bj3 = min_ab(min_ab(min_ab(min_ab(fabs(x[q3] - x1), fabs(x[q3] - x2)), min_ab(fabs(y[q3] - yu), fabs(y[q3] - y2))), sqrt((x[q3] - x[q1]) * (x[q3] - x[q1]) + (y[q3] - y[q1]) * (y[q3] - y[q1])) - bj1), sqrt((x[q3] - x[q2]) * (x[q3] - x[q2]) + (y[q3] - y[q2]) * (y[q3] - y[q2])) - bj2);
if (sqrt((x[q4] - x[q1]) * (x[q4] - x[q1]) + (y[q4] - y[q1]) * (y[q4] - y[q1])) <= bj1 || sqrt((x[q4] - x[q2]) * (x[q4] - x[q2]) + (y[q4] - y[q2]) * (y[q4] - y[q2])) <= bj2 || sqrt((x[q4] - x[q3]) * (x[q4] - x[q3]) + (y[q4] - y[q3]) * (y[q4] - y[q3])) <= bj3)
bj4 = 0;
else
bj4 = min_ab(min_ab(min_ab(min_ab(min_ab(fabs(x[q4] - x1), fabs(x[q4] - x2)), min_ab(fabs(y[q4] - yu), fabs(y[q4] - y2))), sqrt((x[q4] - x[q1]) * (x[q4] - x[q1]) + (y[q4] - y[q1]) * (y[q4] - y[q1])) - bj1), sqrt((x[q4] - x[q2]) * (x[q4] - x[q2]) + (y[q4] - y[q2]) * (y[q4] - y[q2])) - bj2), sqrt((x[q4] - x[q3]) * (x[q4] - x[q3]) + (y[q4] - y[q3]) * (y[q4] - y[q3])) - bj3);
the_max_num = max_ab(the_max_num, bj1 * bj1 * 3.1415926 + bj2 * bj2 * 3.1415926 + bj3 * bj3 * 3.1415926 + bj4 * bj4 * 3.1415926);
}
if (q == 5)
{
bj1 = min_ab(min_ab(fabs(x[q1] - x1), fabs(x[q1] - x2)), min_ab(fabs(y[q1] - yu), fabs(y[q1] - y2)));
if (sqrt((x[q2] - x[q1]) * (x[q2] - x[q1]) + (y[q2] - y[q1]) * (y[q2] - y[q1])) <= bj1)
bj2 = 0;
else
bj2 = min_ab(min_ab(min_ab(fabs(x[q2] - x1), fabs(x[q2] - x2)), min_ab(fabs(y[q2] - yu), fabs(y[q2] - y2))), sqrt((x[q2] - x[q1]) * (x[q2] - x[q1]) + (y[q2] - y[q1]) * (y[q2] - y[q1])) - bj1);
if (sqrt((x[q3] - x[q1]) * (x[q3] - x[q1]) + (y[q3] - y[q1]) * (y[q3] - y[q1])) <= bj1 || sqrt((x[q3] - x[q2]) * (x[q3] - x[q2]) + (y[q3] - y[q2]) * (y[q3] - y[q2])) <= bj2)
bj3 = 0;
else
bj3 = min_ab(min_ab(min_ab(min_ab(fabs(x[q3] - x1), fabs(x[q3] - x2)), min_ab(fabs(y[q3] - yu), fabs(y[q3] - y2))), sqrt((x[q3] - x[q1]) * (x[q3] - x[q1]) + (y[q3] - y[q1]) * (y[q3] - y[q1])) - bj1), sqrt((x[q3] - x[q2]) * (x[q3] - x[q2]) + (y[q3] - y[q2]) * (y[q3] - y[q2])) - bj2);
if (sqrt((x[q4] - x[q1]) * (x[q4] - x[q1]) + (y[q4] - y[q1]) * (y[q4] - y[q1])) <= bj1 || sqrt((x[q4] - x[q2]) * (x[q4] - x[q2]) + (y[q4] - y[q2]) * (y[q4] - y[q2])) <= bj2 || sqrt((x[q4] - x[q3]) * (x[q4] - x[q3]) + (y[q4] - y[q3]) * (y[q4] - y[q3])) <= bj3)
bj4 = 0;
else
bj4 = min_ab(min_ab(min_ab(min_ab(min_ab(fabs(x[q4] - x1), fabs(x[q4] - x2)), min_ab(fabs(y[q4] - yu), fabs(y[q4] - y2))), sqrt((x[q4] - x[q1]) * (x[q4] - x[q1]) + (y[q4] - y[q1]) * (y[q4] - y[q1])) - bj1), sqrt((x[q4] - x[q2]) * (x[q4] - x[q2]) + (y[q4] - y[q2]) * (y[q4] - y[q2])) - bj2), sqrt((x[q4] - x[q3]) * (x[q4] - x[q3]) + (y[q4] - y[q3]) * (y[q4] - y[q3])) - bj3);
if (sqrt((x[q5] - x[q1]) * (x[q5] - x[q1]) + (y[q5] - y[q1]) * (y[q5] - y[q1])) <= bj1 || sqrt((x[q5] - x[q2]) * (x[q5] - x[q2]) + (y[q5] - y[q2]) * (y[q5] - y[q2])) <= bj2 || sqrt((x[q5] - x[q3]) * (x[q5] - x[q3]) + (y[q5] - y[q3]) * (y[q5] - y[q3])) <= bj3 || sqrt((x[q5] - x[q4]) * (x[q5] - x[q4]) + (y[q5] - y[q4]) * (y[q5] - y[q4])) <= bj4)
bj5 = 0;
else
bj5 = min_ab(min_ab(min_ab(min_ab(min_ab(min_ab(fabs(x[q5] - x1), fabs(x[q5] - x2)), min_ab(fabs(y[q5] - yu), fabs(y[q5] - y2))), sqrt((x[q5] - x[q1]) * (x[q5] - x[q1]) + (y[q5] - y[q1]) * (y[q5] - y[q1])) - bj1), sqrt((x[q5] - x[q2]) * (x[q5] - x[q2]) + (y[q5] - y[q2]) * (y[q5] - y[q2])) - bj2), sqrt((x[q5] - x[q3]) * (x[q5] - x[q3]) + (y[q5] - y[q3]) * (y[q5] - y[q3])) - bj3), sqrt((x[q5] - x[q4]) * (x[q5] - x[q4]) + (y[q5] - y[q4]) * (y[q5] - y[q4])) - bj4);
the_max_num = max_ab(the_max_num, bj1 * bj1 * 3.1415926 + bj2 * bj2 * 3.1415926 + bj3 * bj3 * 3.1415926 + bj4 * bj4 * 3.1415926 + bj5 * bj5 * 3.1415926);
}
if (q == 6)
{
bj1 = min_ab(min_ab(fabs(x[q1] - x1), fabs(x[q1] - x2)), min_ab(fabs(y[q1] - yu), fabs(y[q1] - y2)));
if (sqrt((x[q2] - x[q1]) * (x[q2] - x[q1]) + (y[q2] - y[q1]) * (y[q2] - y[q1])) <= bj1)
bj2 = 0;
else
bj2 = min_ab(min_ab(min_ab(fabs(x[q2] - x1), fabs(x[q2] - x2)), min_ab(fabs(y[q2] - yu), fabs(y[q2] - y2))), sqrt((x[q2] - x[q1]) * (x[q2] - x[q1]) + (y[q2] - y[q1]) * (y[q2] - y[q1])) - bj1);
if (sqrt((x[q3] - x[q1]) * (x[q3] - x[q1]) + (y[q3] - y[q1]) * (y[q3] - y[q1])) <= bj1 || sqrt((x[q3] - x[q2]) * (x[q3] - x[q2]) + (y[q3] - y[q2]) * (y[q3] - y[q2])) <= bj2)
bj3 = 0;
else
bj3 = min_ab(min_ab(min_ab(min_ab(fabs(x[q3] - x1), fabs(x[q3] - x2)), min_ab(fabs(y[q3] - yu), fabs(y[q3] - y2))), sqrt((x[q3] - x[q1]) * (x[q3] - x[q1]) + (y[q3] - y[q1]) * (y[q3] - y[q1])) - bj1), sqrt((x[q3] - x[q2]) * (x[q3] - x[q2]) + (y[q3] - y[q2]) * (y[q3] - y[q2])) - bj2);
if (sqrt((x[q4] - x[q1]) * (x[q4] - x[q1]) + (y[q4] - y[q1]) * (y[q4] - y[q1])) <= bj1 || sqrt((x[q4] - x[q2]) * (x[q4] - x[q2]) + (y[q4] - y[q2]) * (y[q4] - y[q2])) <= bj2 || sqrt((x[q4] - x[q3]) * (x[q4] - x[q3]) + (y[q4] - y[q3]) * (y[q4] - y[q3])) <= bj3)
bj4 = 0;
else
bj4 = min_ab(min_ab(min_ab(min_ab(min_ab(fabs(x[q4] - x1), fabs(x[q4] - x2)), min_ab(fabs(y[q4] - yu), fabs(y[q4] - y2))), sqrt((x[q4] - x[q1]) * (x[q4] - x[q1]) + (y[q4] - y[q1]) * (y[q4] - y[q1])) - bj1), sqrt((x[q4] - x[q2]) * (x[q4] - x[q2]) + (y[q4] - y[q2]) * (y[q4] - y[q2])) - bj2), sqrt((x[q4] - x[q3]) * (x[q4] - x[q3]) + (y[q4] - y[q3]) * (y[q4] - y[q3])) - bj3);
if (sqrt((x[q5] - x[q1]) * (x[q5] - x[q1]) + (y[q5] - y[q1]) * (y[q5] - y[q1])) <= bj1 || sqrt((x[q5] - x[q2]) * (x[q5] - x[q2]) + (y[q5] - y[q2]) * (y[q5] - y[q2])) <= bj2 || sqrt((x[q5] - x[q3]) * (x[q5] - x[q3]) + (y[q5] - y[q3]) * (y[q5] - y[q3])) <= bj3 || sqrt((x[q5] - x[q4]) * (x[q5] - x[q4]) + (y[q5] - y[q4]) * (y[q5] - y[q4])) <= bj4)
bj5 = 0;
else
bj5 = min_ab(min_ab(min_ab(min_ab(min_ab(min_ab(fabs(x[q5] - x1), fabs(x[q5] - x2)), min_ab(fabs(y[q5] - yu), fabs(y[q5] - y2))), sqrt((x[q5] - x[q1]) * (x[q5] - x[q1]) + (y[q5] - y[q1]) * (y[q5] - y[q1])) - bj1), sqrt((x[q5] - x[q2]) * (x[q5] - x[q2]) + (y[q5] - y[q2]) * (y[q5] - y[q2])) - bj2), sqrt((x[q5] - x[q3]) * (x[q5] - x[q3]) + (y[q5] - y[q3]) * (y[q5] - y[q3])) - bj3), sqrt((x[q5] - x[q4]) * (x[q5] - x[q4]) + (y[q5] - y[q4]) * (y[q5] - y[q4])) - bj4);
if (sqrt((x[q6] - x[q1]) * (x[q6] - x[q1]) + (y[q6] - y[q1]) * (y[q6] - y[q1])) <= bj1 || sqrt((x[q6] - x[q2]) * (x[q6] - x[q2]) + (y[q6] - y[q2]) * (y[q6] - y[q2])) <= bj2 || sqrt((x[q6] - x[q3]) * (x[q6] - x[q3]) + (y[q6] - y[q3]) * (y[q6] - y[q3])) <= bj3 || sqrt((x[q6] - x[q4]) * (x[q6] - x[q4]) + (y[q6] - y[q4]) * (y[q6] - y[q4])) <= bj4 || sqrt((x[q6] - x[q5]) * (x[q6] - x[q5]) + (y[q6] - y[q5]) * (y[q6] - y[q5])) <= bj5)
bj6 = 0;
else
bj6 = min_ab(min_ab(min_ab(min_ab(min_ab(min_ab(min_ab(fabs(x[q6] - x1), fabs(x[q6] - x2)), min_ab(fabs(y[q6] - yu), fabs(y[q6] - y2))), sqrt((x[q6] - x[q1]) * (x[q6] - x[q1]) + (y[q6] - y[q1]) * (y[q6] - y[q1])) - bj1), sqrt((x[q6] - x[q2]) * (x[q6] - x[q2]) + (y[q6] - y[q2]) * (y[q6] - y[q2])) - bj2), sqrt((x[q6] - x[q3]) * (x[q6] - x[q3]) + (y[q6] - y[q3]) * (y[q6] - y[q3])) - bj3), sqrt((x[q6] - x[q4]) * (x[q6] - x[q4]) + (y[q6] - y[q4]) * (y[q6] - y[q4])) - bj4), sqrt((x[q6] - x[q5]) * (x[q6] - x[q5]) + (y[q6] - y[q5]) * (y[q6] - y[q5])) - bj5);
the_max_num = max_ab(the_max_num, bj1 * bj1 * 3.1415926 + bj2 * bj2 * 3.1415926 + bj3 * bj3 * 3.1415926 + bj4 * bj4 * 3.1415926 + bj5 * bj5 * 3.1415926 + bj6 * bj6 * 3.1415926);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
cin >> x1 >> yu >> x2 >> y2;
for (int i = 1; i <= n; i++)
cin >> x[i] >> y[i];
switch (n)
{
case 1:
sc(n, 1, 0, 0, 0, 0, 0);
break;
case 2:
for (int i1 = 1; i1 <= n; i1++)
for (int i2 = 1; i2 <= n; i2++)
{
if (i2 == i1)
continue;
sc(n, i1, i2, 0, 0, 0, 0);
}
break;
case 3:
for (int i1 = 1; i1 <= n; i1++)
for (int i2 = 1; i2 <= n; i2++)
{
if (i2 == i1)
continue;
for (int i3 = 1; i3 <= n; i3++)
{
if (i3 == i1 || i3 == i2)
continue;
sc(n, i1, i2, i3, 0, 0, 0);
}
}
break;
case 4:
for (int i1 = 1; i1 <= n; i1++)
for (int i2 = 1; i2 <= n; i2++)
{
if (i2 == i1)
continue;
for (int i3 = 1; i3 <= n; i3++)
{
if (i3 == i1 || i3 == i2)
continue;
for (int i4 = 1; i4 <= n; i4++)
{
if (i4 == i1 || i4 == i2 || i4 == i3)
continue;
sc(n, i1, i2, i3, i4, 0, 0);
}
}
}
break;
case 5:
for (int i1 = 1; i1 <= n; i1++)
for (int i2 = 1; i2 <= n; i2++)
{
if (i2 == i1)
continue;
for (int i3 = 1; i3 <= n; i3++)
{
if (i3 == i1 || i3 == i2)
continue;
for (int i4 = 1; i4 <= n; i4++)
{
if (i4 == i1 || i4 == i2 || i4 == i3)
continue;
for (int i5 = 1; i5 <= n; i5++)
{
if (i5 == i1 || i5 == i2 || i5 == i3 || i5 == i4)
continue;
sc(n, i1, i2, i3, i4, i5, 0);
}
}
}
}
break;
case 6:
for (int i1 = 1; i1 <= n; i1++)
for (int i2 = 1; i2 <= n; i2++)
{
if (i2 == i1)
continue;
for (int i3 = 1; i3 <= n; i3++)
{
if (i3 == i1 || i3 == i2)
continue;
for (int i4 = 1; i4 <= n; i4++)
{
if (i4 == i1 || i4 == i2 || i4 == i3)
continue;
for (int i5 = 1; i5 <= n; i5++)
{
if (i5 == i1 || i5 == i2 || i5 == i3 || i5 == i4)
continue;
for (int i6 = 1; i6 <= n; i6++)
{
if (i6 == i1 || i6 == i2 || i6 == i3 || i6 == i4 || i6 == i5)
continue;
sc(n, i1, i2, i3, i4, i5, i6);
}
}
}
}
}
break;
}
cout << (int)round(fabs(x1 - x2) * fabs(yu - y2) - the_max_num);
return 0;
}
double max_ab(double x, double y)
{
return (x > y ? x : y);
}
double min_ab(double x, double y)
{
return (x > y ? y : x);
}