ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1185. Wall

Mayday! Mayday! Mayday! Help me!!! I got CRUSH?!?
Послано nullman 30 май 2002 03:38
1) I tried to increase the array up to 1010 but notheing changed.
2) I tried C++ 'vector' by '.push_back()' => CRUSH again.

I have no idea!!!

My new C++ code:

// Do not pay attention to the input file!!!

#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
using namespace std;

#define pi acos(-1)
#define lin(a,b,c) (a.x*b.y-b.x*a.y+c.y*(b.x-a.x)+c.x*(a.y-b.y))
#define eq(a,b) ((a.x==b.x && a.y==b.y)?1:0)

typedef struct {double x; double y;} P;

int n;
double res;
vector<int> InUse;
vector<P> pArr;

double sqr(double x) {
  return x*x;
}

double len(P a, P b) {
  return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}

void FindMaxPoly(void) {
  P tmp;
  int i, j;

  for (i=0,tmp=pArr[0];i<n;i++) {
    if (pArr[i].x>tmp.x) j=i;
    InUse.push_back(0);
  }
  tmp=pArr[j]; InUse[j]=1;

  while (1) {
    if (eq(tmp,pArr[0])==0) j=0;
    else j=1;
    for (i=0;i<n;i++)
      if ( eq(pArr[i],pArr[j])==0 &&
           eq(pArr[i],tmp)==0 &&
           lin(tmp,pArr[j],pArr[i]) < 0
         ) j=i;
    if (InUse[j]) break;
    InUse[j]=1; tmp=pArr[j];
  }
}

int main(void) {
  int i,r;
  P last,pp;
  fstream f("WALL.IN",ios::in);
  f>>n>>r;
  for (i=0;i<n;i++) {
    f>>pp.x>>pp.y;
    pArr.push_back(pp);
  }
  FindMaxPoly();
  res=2*pi*r; i=0;
  while (InUse[i]==0) i++;
  pArr.push_back(pArr[i]);
  InUse.push_back(1);
  last=pArr[i++];
  for (;i<=n;i++)
    if (InUse[i]) {
      res+=len(last,pArr[i]);
      last=pArr[i];
    }
  cout<<floor(res);
  //cin.get(); cin.get();
  return 0;
}