Отримання знань

дистанційна підтримка освіти школярів


Забор
http://acm.pku.edu.cn/JudgeOnline/problem?id=1031

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на Pascal:

const
eps = 1e-10;
maxn = 100;

type
real = extended;

function det ( x11, x12, x21, x22: real ): real;
begin
det:= x11*x22 - x12*x21;
end;

function Angle ( x, y: real ): real; { angle in [0;2*pi) range }
var
ang: real;
begin
if abs(x) < eps then
if y > 0 then
Angle:= pi/2
else
Angle:= 3*pi/2
else begin
ang:= arctan ( y / x );
if x < 0 then
ang:= pi + ang;
if ang < 0 then
ang:= ang + 2*pi;
Angle:= ang;
end;
end;

procedure Swap ( var x, y: real );
var
t: real;
begin
t:= x;
x:= y;
y:= t;
end;

{ getAngInt - returns the interval for angles }
procedure getAngInt ( x1, y1, x2, y2: real; var a1, a2: real );
begin
if det ( x1, y1, x2, y2 ) < eps then begin
swap ( x1, x2 );
swap ( y1, y2 );
end;
a1:= Angle ( x1, y1 );
a2:= Angle ( x2, y2 );
if a2 < a1 - eps then
a2:= a2 + 2*pi;
end;

function min( x, y: real ): real;
begin
if x < y then
min:= x
else
min:= y;
end;

function max(x, y: real): real;
begin
if x > y then
max:= x
else
max:= y;
end;

function between ( a, x, b: real ): boolean;
begin
between:= (x > a - eps) and (x < b + eps);
end;

var
k, h: real;
n, i, j: integer;
x, y: array[0..maxn] of real;
a, b, aa, bb: real;

begin

{ Reading input }
read ( k, h, n );
for i:= 1 to n do
read ( x[i], y[i] );
x[0]:= x[n];
y[0]:= y[n];

{ Solving }
getAngInt ( x[0], y[0], x[1], y[1], a, b ); { [a,b] - current interval }
for i:= 1 to n-1 do begin
getAngInt ( x[i], y[i], x[i+1], y[i+1], aa, bb );
{ Now we shall unite [aa,bb] with [a,b] }
for j:= -1 to 1 do
if between ( a, aa + 2*pi*j, b ) or between ( a, bb + 2*pi*j, b ) then begin
a:= min ( a, aa + 2*pi*j );
b:= max ( b, bb + 2*pi*j );
break;
end;
end;

{ Interval of angles found, let's write the answer }
writeln ( min ( b - a, 2*pi ) * k * h:0:2 );
end.

   Пример решения на C++:

#include < iostream >
#include < cmath >
using namespace std;
 
#define out(x) (cout << #x << ": " << x << endl)
typedef long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template <class T> void show(T a, int n) { for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template <class T> void show(T a, int r, int l) { for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }
 
const double eps = 1e-10;
const double pi = acos(-1.0);
const int maxn = 110;
 
typedef struct point_t
{
    double x, y;
};
 
typedef struct interval_t
{
    double l, r;
};
 
double get_angle(double x, double y)
{
    if (abs(x) < eps)
    {
        if (y > 0) return pi / 2.0;
        else return 3.0 * pi / 2.0;
    }
    else
    {
        double t = atan(y / x);
        if (x < 0)
            t += pi;
        if (t < 0) t += 2.0 * pi;
        return t;
    }
}
 
interval_t get_range(point_t a, point_t b)
{
    if (a.x * b.y - a.y * b.x < eps)
    {
        swap(a, b);
    }
    double t1 = get_angle(a.x, a.y);
    double t2 = get_angle(b.x, b.y);
    if (t2 < t1 - eps) t2 += 2.0 * pi;
    interval_t ret;
    ret.l = t1;
    ret.r = t2;
    return ret;
}
 
bool operator <(const interval_t &a, const interval_t &b)
{
    return a.l < b.l || a.l == b.l && a.r < b.r;
}
 
bool between(const double &a, const double &x, const double &b)
{
    return x > a - eps && x < b + eps;
}
 
point_t p[maxn];
interval_t interval[maxn];
 
int main()
{
    double k, h;
    int n;
    scanf("%lf%lf%d", &k, &h, &n);
    {
        for (int i = 0; i < n; i++)
            scanf("%lf%lf", &p[i].x, &p[i].y);
        for (int i = 0; i < n; i++)
            interval[i] = get_range(p[i], p[(i + 1) % n]);
       
        double l = interval[0].l, r = interval[0].r;
        for (int i = 1; i < n; i++)
        {
            for (int j = -1; j <= 1; j++)
            {
                if (between(l, interval[i].l + j * 2 * pi, r) || between(l, interval[i].r + j * 2 * pi, r))
                {
                    l = min(l, interval[i].l + j * 2 * pi);
                    r = max(interval[i].r + j * 2 * pi, r);
                    break;
                }
            }
        }
        printf("%.2lf\n", min(r - l, 2.0 * pi) * k * h);
    }
    return 0;
}

Попередня Зміст Наступна
В системі: гості - (1); користувачі - (0)