Задачи для подготовки

Занятие № 5

Задачи на плоскости.

Пример 1
Даны 3 точки A, B и C. Определить, лежат ли они на одной прямой.
Все точки задаются своими координатами – парами целых чисел.
Решение

type
    point = record
        x, y: integer;
    end;

function isLine (A, B, C: point) : boolean;
begin
    isLine := ((B.x - A.x) * (C.y - A.y) - C.x - A.x) * (B.y - A.y) = 0);
end;

Пример 2
Решение

function isClockWise (A, B, C: point): boolean;
begin
    isClockWise := ((B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y) < 0);
end;

Пример 3
a)Даны 4 точки A, B, C и D. Определить, пересекаются ли отрезки AC и BD.
b)Даны 4 точки A, B, C и D. Определить, является ли четырехугольник ABCD выпуклым.
Замечание: если 3 или все 4 вершины оказываются на одной прямой, то четырехугольник считается выпуклым.
Решение
Отрезки AC и BD пересекаются тогда и только тогда, когда четырехугольник ABCD выпуклый, так что это одна и та же задача. Это верно, по крайней мере, если не обращать внимания на особые случаи, то есть на ситуации, когда точки лежат на одной прямой. Такие случаи можно разобрать отдельно.
Для того, чтобы четырехугольник ABCD был выпуклым, необходимо и достаточно, чтобы все 4 обхода `A->B->C,\ B->C->D,\ C->D->A,\ D->A->B` были бы обходами в одну сторону: либо по часовой стрелке, либо против.

Приведем пример функции, где мы используем знакомый уже тип point и функцию из предыдущего задания.

function isConvex4(A, B, C, D: point): boolean;
begin
    if (isClockWise(A, B, C)) then
        isConvex4 := isClockWise(B, C, D) and
                     isClockWise(C, D, A) and
                     isClockWise(D, A, B)
    else
        isConvex4 := (not isClockWise(B, C, D)) and
                     (not isClockWise(C, D, A)) and
                     (not isClockWise(D, A, B));
end;

Эта функция работает в не особых случаях. Программа, которая удовлетворяет требованию задания может, например, проверять сначала, не лежат ли какие-то 3 точки на одной прямой, вызывая 4 раза функцию isLine.

#include <stdio.h>
#include "math.h"

void N(double &a, double &b)
{
  double c;

  if(a<b){
    c=a;
    a=b;
    b=c;
  }
}

int main(){
  double P[3], gl, o;
  scanf("%lf%lf%lf", &P[0],&P[1],&P[2]);
  N(P[0],P[1]);
  N(P[0],P[2]);
  N(P[1],P[2]);
  gl=acos((P[1]*P[1]+P[0]*P[0]-P[2]*P[2])/2/P[1]/P[0]);
  if(gl>asin(1.0)/2)o=P[0]*P[0]/4;
  else{	if(cos(gl)*P[0]<=P[1])
           o=sin(gl)*P[0]*cos(gl)*P[0]/2;
	else o=tan(gl)*P[1]*P[1]/2;
      }
  printf("%0.6f", o);
}

Системы счисления

{$R-}
var
  i, j, alen, blen: longint;
  a, b: array[1..30000] of byte;

procedure readnum;
var
  c: char;
  hi, lo, buf: longint;
begin
  hi := 0;
  while not eoln do 
  begin
    read(c);
    inc(hi);
    case c of
      '0'..'9': a[hi] := ord(c) - ord('0');
      'A'..'Z': a[hi] := ord(c) - ord('A') + 10;
    end;
  end;
  alen := hi;
  lo := 1;
  while lo < hi do 
  begin
    buf := a[hi];
    a[hi] := a[lo];
    a[lo] := buf;
    inc(lo); dec(hi);
  end;
end;

function ZeroA: boolean;
var
  index: longint;
begin
  ZeroA := false;
  for index := 1 to alen do
    if a[index] <> 0 then
      exit;
  ZeroA := true;
end;

function reminder: longint;
var
  rem, index: longint;
begin
  rem := 0;
  for index := alen downto 1 do 
  begin
    rem := rem * i + a[index];
    a[index] := rem div j;
    rem := rem mod j;
  end;
  reminder := rem;
end;

procedure printB;
var
  index, i: longint;
  c: char;
begin
  for index := 30000 downto 1 do
    if b[index] <> 0 then
      break;
  for i := index downto 1 do 
  begin
    case b[i] of
      0..9: c := chr(b[i] + ord('0'));
      10..35: c := chr(b[i] - 10 + ord('A'));
    end;
    write(c);
  end;
end;

begin
  assign(input, 'input.txt'); reset(input);
  assign(output, 'output.txt'); rewrite(output);
  readln(i, j);
  readnum;
  blen := 0;
  repeat
    inc(blen);
    b[blen] := reminder;
  until ZeroA;
  printB;
end.