Решение задачи Дачники с Acmp

Без пояснения   Просмотров: 64


Всем известно, что дачники – народ странный, почти такой же, как и программисты. Строят они свои дачи непонятно где, да и выращивают там непонятно что и непонятно зачем. А уж как они туда добираются, это другая история: кто на автобусе, кто на электричке, кто на автомобиле, ну а кто-то вовсе пешком ходит от дома и до самого участка. Так что не стоит удивляться, если вдруг Вы узнаете, что некое садоводческое товарищество располагается на острове, а дачники добираются до него самолетом. Да еще и на этом острове может не быть посадочной полосы, так что высадиться на остров можно, только прыгая с парашютом (мы уж не рассматриваем то, как они возвращаются с дач домой). Рассмотрим этот уникальный случай. Пилот всегда старается осуществить высадку парашютистов таким образом, чтобы дачники приземлялись как можно ближе к своим прямоугольным участкам. Пилоту интересно знать: сколько дачников приземлится на свои участки? Помогите ему решить эту задачу!

Код

#include <cmath>
#include <iostream>
#include <fstream>
using namespace std;
struct Point {
  double x, y;
};
double triangleSqr(Point a, Point b, Point c) {
  return abs(0.5*((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y)));
}
int main() {
  const double limit(10e-8);
  
  ifstream in("input.txt");
  ofstream out("output.txt");
  
  Point a, b, c, d, person;
  int N, k = 0;
  in >> N;
  
  for (int i = 0; i < N; i++) {
    in >> person.x >> person.y >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y >> d.x >> d.y;
    
    double S = triangleSqr(a, b, c) + triangleSqr(b, c, d);
    double PersonS = triangleSqr(a, b, person) + triangleSqr(b, c, person) + 
      triangleSqr(c, d, person) + triangleSqr(d, a, person);
    
    if (PersonS - S <= limit)
      ++k;
  } 
  out << k;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться