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

Обсуждение задачи 1588. Ямайка

My AC code !!!
Послано AYUBXON UBAYDULLAYEV (TUIT of IT) 14 мар 2012 21:12
#include<iostream>
#include<math.h>
#include<algorithm>
void quickSort(double x[],double y[],int left, int right) {
      int i = left, j = right;
      double tmp;
      double pivot = x[(left + right) / 2];
      while (i <= j) {
            while (x[i] < pivot)
                  i++;
            while (x[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = x[i]; x[i] = x[j]; x[j] = tmp;
                  tmp = y[i]; y[i] = y[j]; y[j] = tmp;
                  i++;
                  j--;
            }
      };
      if (left < j)    quickSort(x,y,left, j);
      if (i < right)   quickSort(x,y,i, right);
}
double dis(double x1,double y1,double x2,double y2)
{
  return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
using namespace std;
int main()
{
   double a[305][305],x[305],y[305],max,s1;
   int i,j,n,k;
   cin>>n;
   for(i=1;i<=n;i++)cin>>x[i]>>y[i];
   quickSort(x,y,1,n);
   int left=1,right=1;
   for(i=2;i<=n;i++)
   {
      if(x[i]==x[i-1])right++;
      else
      {
          sort(y+left,y+right+1);
          right++;
          left=right;
      }
   }
   sort(y+left,y+right+1);
   for(i=1;i<n;i++)
   for(j=i+1;j<=n;j++)
   a[i][j]=dis(x[i],y[i],x[j],y[j]);
   for(i=1;i<n-1;i++)
   for(j=i+1;j<n;j++)
   {
     max=a[i][j];
     bool f=0;
     for(k=j+1;k<=n;k++)
     if ((x[k]-x[i])*(y[i]-y[j])==(y[k]-y[i])*(x[i]-x[j]))
     {
       if (max<a[i][k]) max=a[i][k];else a[i][k]=0;
       if (max<a[j][k]) max=a[j][k];else a[j][k]=0;
     }
     if (max>a[i][j]) a[i][j]=0;
   }
   s1=0;
   for(i=1;i<n;i++)
   for(j=i+1;j<=n;j++)s1+=a[i][j];
   s1=s1+0.4999999999;
   cout<<(long long)s1;
   system("pause");
   return 0;
}
Re: My AC code !!!
Послано Sunnat 15 мар 2012 00:59
#include<cstdio>
#include<cmath>
int main()
{
    double x[300],y[300];
    double l[300][300],m,s=0;
    int n,k,i,j;
    scanf("%i",&n);
    for(i=0;i<n;i++)
    {
       scanf("%lf%lf",&x[i],&y[i]);
       j=i;
       while(j&&(x[j]<x[j-1]||(x[j]==x[j-1]&&y[j]<y[j-1])))
       {
           x[j]=x[j]+x[j-1];x[j-1]=x[j]-x[j-1];x[j]=x[j]-x[j-1];
           y[j]=y[j]+y[j-1];y[j-1]=y[j]-y[j-1];y[j]=y[j]-y[j-1];
           j--;
       }
    }
    for(i=0;i<n-1;i++)
      for(j=0;j<n;j++)
        l[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
    for(i=0;i<n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
            if(!l[i][j])continue;
            m=l[i][j];
            for(k=j+1;k<n;k++)
            {
              if((x[i]-x[j])*(y[k]-y[j])==(x[k]-x[j])*(y[i]-y[j]))
              {
                (l[i][k]>m)?m=l[i][k]:l[i][k]=0;
                (l[j][k]>m)?m=l[j][k]:l[j][k]=0;
              }
            }
            if(l[i][j]<m)l[i][j]=0;
            s+=l[i][j];
        }
    }
    printf("%.lf",s);
    return 0;
}
Re: My AC code !!!
Послано ASK 16 фев 2014 19:51
There is no need to reinvent the wheel, that is a half of the program devoted to sorting can be replaced with

  struct P{ double x,y; };
  P p[n]; F(i,n) cin >> p[i].x >> p[i].y;
  sort(p, p+n, [](const P& a, const P& b){ return tie(a.x,a.y) < tie(b.x,b.y); });

To reduce number of possible typos, use macros, such as

#define I(x) int x; cin >> x
#define F(i,n) for(int i = 0; i < (n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)

Finally, "do not post AC solutions" :-)