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

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


Поиск сокровищ
http://acm.pku.edu.cn/JudgeOnline/problem?id=1066

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

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

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

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

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

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

program PKU1066;
const maxn = 200;
maxm = 100000;
error = 1e-7;

type integer = longint;
node = array[1 .. 2] of double;
arr = array[1 .. maxm] of integer;

var g, q, c, l, r, dep, tow, next, pre, start: arr;
w: array[1 .. maxm] of boolean;
d: array[1 .. maxm] of double;
h: array[0 .. 100, 0 .. 100] of integer;
ver: array[1 .. maxm] of node;
a: array[1 .. maxn, 1 .. 2] of integer;
n, m, len, tot, inside, outside, totnode: integer;
treasure: node;

function same(i, j: double): boolean;
begin
same := abs(i - j) < error;
end;

function find(x, y: double): integer;
var u, v, tmp: integer;
begin
u := trunc(x); v := trunc(y);
tmp := h[u, v];
while tmp <> 0 do begin
if same(ver[tmp, 1], x) and same(ver[tmp, 2], y) then begin
find := tmp;
exit;
end;
tmp := pre[tmp];
end;
totnode := totnode + 1;
ver[totnode, 1] := x; ver[totnode, 2] := y;
pre[totnode] := h[u, v];
h[u, v] := totnode; find := totnode;
end;

procedure updata;
var i, p, q, u, v, x0, y0, x1, y1: integer;
begin
fillchar(g, sizeof(g), 0);
fillchar(h, sizeof(h), 0);
read(n); totnode := 0;
for i := 1 to n do begin
read(x0, y0, x1, y1);
u := find(x0, y0);
v := find(x1, y1);
a[i, 1] := u; a[i, 2] := v;
end;
u := find(0, 0); v := find(100, 0);
p := find(100, 100); q := find(0, 100);
a[n + 1, 1] := u; a[n + 1, 2] := v;
a[n + 2, 1] := v; a[n + 2, 2] := p;
a[n + 3, 1] := p; a[n + 3, 2] := q;
a[n + 4, 1] := q; a[n + 4, 2] := u;
n := n + 4;
readln(treasure[1], treasure[2]);
end;

function area(var i, j, k: node): double;
begin
area := (j[1] - i[1]) * (k[2] - i[2]) - (j[2] - i[2]) * (k[1] - i[1]);
end;

var k1, k2, k3, k4: double;

procedure check(i, j: integer);
var x0, y0: double;
k: integer;
begin
k1 := area(ver[a[i, 1]], ver[a[i, 2]], ver[a[j, 1]]);
k2 := area(ver[a[i, 1]], ver[a[i, 2]], ver[a[j, 2]]);
k3 := area(ver[a[j, 1]], ver[a[j, 2]], ver[a[i, 1]]);
k4 := area(ver[a[j, 1]], ver[a[j, 2]], ver[a[i, 2]]);
if (k1 * k2 <= error) and (k3 * k4 <= error) then begin
x0 := (ver[a[j, 1], 1] * k2 - ver[a[j, 2], 1] * k1) / (k2 - k1);
y0 := (ver[a[j, 1], 2] * k2 - ver[a[j, 2], 2] * k1) / (k2 - k1);
k := find(x0, y0);
len := len + 1; c[len] := k;
end;
end;

procedure insert(u, v: integer);
begin
tot := tot + 1;
tow[tot] := v; next[tot] := g[u];
g[u] := tot;
end;

var temp: integer;
temp2: double;

procedure swap(var i, j: integer);
begin
temp := i; i := j; j := temp;
end;

procedure swapreal(var i, j: double);
begin
temp2 := i; i := j; j := temp2;
end;

function compare(i, j: integer): boolean;
begin
compare := (ver[i, 1] < ver[j, 1] - error) or same(ver[i, 1], ver[j, 1]) and (ver[i, 2] < ver[j, 2] - error);
end;

procedure sortv(ll, rr: integer);
var i, j, mid: integer;
begin
i := ll; j := rr; mid := c[(ll + rr) shr 1];
while i <= j do begin
while compare(c[i], mid) do i := i + 1;
while compare(mid, c[j]) do j := j - 1;
if i <= j then begin
swap(c[i], c[j]);
i := i + 1; j := j - 1;
end;
end;
if i < rr then sortv(i, rr);
if ll < j then sortv(ll, j);
end;

procedure sorte(ll, rr: integer);
var i, j: integer;
mid: double;
begin
i := ll; j := rr; mid := d[(ll + rr) shr 1];
while i <= j do begin
while d[i] < mid - error do i := i + 1;
while d[j] > mid + error do j := j - 1;
if i <= j then begin
swap(c[i], c[j]); swapreal(d[i], d[j]);
i := i + 1; j := j - 1;
end;
end;
if i < rr then sorte(i, rr);
if ll < j then sorte(ll, j);
end;

function calc(var p, q: node): double;
var x0, y0: double;
begin
x0 := q[1] - p[1]; y0 := q[2] - p[2];
if same(x0, 0) then
if y0 > 0 then calc := pi / 2
else calc := pi * 3 / 2
else begin
temp2 := arctan(y0 / x0);
if x0 < 0 then temp2 := temp2 + pi;
if temp2 < 0 then temp2 := temp2 + pi * 2;
if temp2 >= 2 * pi then temp2 := temp2 - pi * 2;
calc := temp2;
end;
end;

procedure prepare;
var i, j, now, tmp: integer;
begin
tot := 0;
for i := 1 to n do begin
len := 0;
for j := 1 to n do if i <> j then
check(i, j);
if len > 1 then sortv(1, len);
now := c[1];
for j := 2 to len do if c[j] <> now then begin
insert(now, c[j]);
insert(c[j], now);
now := c[j];
end;
end;
now := 1;
for i := 1 to totnode do begin
tmp := g[i]; start[i] := now;
while tmp <> 0 do begin
c[now] := tow[tmp];
d[now] := calc(ver[i], ver[tow[tmp]]);
now := now + 1;
tmp := next[tmp];
end;
sorte(start[i], now - 1);
end; start[totnode + 1] := now;
end;

procedure bfs;
var open, closed, tmp, u, v: integer;
begin
fillchar(dep, sizeof(dep), 0);
open := 0; closed := 1;
q[1] := outside; dep[outside] := 1;
while (open < closed) and (dep[inside] = 0) do begin
open := open + 1; u := q[open];
tmp := g[u];
while tmp <> 0 do begin
v := tow[tmp];
if dep[v] = 0 then begin
dep[v] := dep[u] + 1;
closed := closed + 1;
q[closed] := v;
end;
tmp := next[tmp];
end;
end;
writeln('Number of doors = ', dep[inside] - 1);
end;

procedure main;
var i, j, u, v, k: integer;
begin
fillchar(g, sizeof(g), 0);
fillchar(l, sizeof(l), 0);
fillchar(r, sizeof(r), 0);
fillchar(w, sizeof(w), true);
m := 0; tot := 0;
for i := 1 to totnode do begin
for j := start[i] to start[i + 1] - 1 do if l[j] = 0 then begin
m := m + 1; l[j] := m;
u := i; v := c[j];
repeat
if area(ver[u], ver[v], treasure) < error then w[m] := false;
for k := start[v] to start[v + 1] - 1 do if c[k] = u then break;
r[k] := m; k := k - 1;
if k < start[v] then k := start[v + 1] - 1;
if l[k] = 0 then l[k] := m else break;
u := v; v := c[k];
until false;
end;
end;
u := find(0, 0);
for k := start[u] to start[u + 1] - 1 do if ver[c[k], 2] = 0 then break;
outside := r[k];
for k := 1 to m do if w[k] and (k <> outside) then inside := k;
for k := 1 to start[totnode] - 1 do begin
insert(l[k], r[k]);
insert(r[k], l[k]);
end;
bfs;
end;

begin
updata;
prepare;
main;
end.

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

#include "iostream"
#include "cmath"
#include "algorithm"
using namespace std;
double const EPS = 1e-8;
const int INF = 0xf777777;
#define zero(x) (((x)>0?(x):-(x))<eps)

struct Point
{
    double x,y;
    Point(){}
       Point(double a, double b):x(a), y(b){}
       bool operator<(Point a){return atan2(y - 50, x - 50) < atan2(a.y - 50, a.x - 50); }
};

struct Line
{              
    Point a, b;
    Line() {}
    Line(Point p10, Point p20): a(p10), b(p20) {} 
};


Point mypoint[64], s, t;
Line myline[30];
int n, countnum, minnum;

double xmult(Point p1, Point p2 , Point p0)
{
    return (p1.x - p0.x)*(p2.y - p0.y)-(p2.x - p0.x)*(p1.y - p0.y);
}
int same_side(Point p1,Point p2,Line l)
{
    return xmult(l.a,p1,l.b)*xmult(l.a,p2,l.b)>EPS;
}

int main()
{
    int i, j, ans;
    minnum = INF; countnum = 0;
    mypoint[countnum++] = Point(0, 0);
    mypoint[countnum++] = Point(100, 0);
    mypoint[countnum++] = Point(0, 100);
    mypoint[countnum++] = Point(100, 100);
   
    cin >> n;
    for(i = 0; i < n; i++)
    {
        scanf("%lf%lf%lf%lf",&myline[i].a.x ,&myline[i].a.y ,&myline[i].b.x ,&myline[i].b.y);
        mypoint[countnum++] = myline[i].a;
        mypoint[countnum++] = myline[i].b;
    }
    scanf("%lf%lf",&s.x,&s.y);
   
       sort(mypoint, mypoint+countnum);
      
       for(i=0; i < countnum; i++ )
       {
           ans = 0;
           t = Point( (mypoint[i].x + mypoint[(i+1)%countnum].x)/2, (mypoint[i].y + mypoint[(i+1)%countnum].y)/2 );
           for(j = 0; j < n; j++)         
               if(!same_side(s, t, myline[j]))
                   ans++;
            if(ans < minnum) minnum = ans;
       }
      
       printf("Number of doors = %d\n", minnum+1);
       return 0;
}
 

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