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

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

Why I got wa on test#4?
Послано panrui 27 дек 2007 20:20
#include<iostream>
#include<math.h>
#define MAX 200000
#define N 350
using namespace std;
int n;
double map1[N][N];
struct node
{
    int x,y;
}point[N];
double dist(node a,node b)
{
    return sqrt((double)((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y)));
}
void init()
{
    cin>>n;
    int i,j;
    for(i=1;i<=n;i++)
        cin>>point[i].x>>point[i].y;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            map1[i][j]=dist(point[i],point[j]);
            //cout<<map1[i][j]<<" ";
        }
        //cout<<endl;
    }
}
double calck(node a,node b)
{
    if(a.x-b.x!=0) return (a.y-b.y)/(a.x-b.x);else return -MAX;
}
int mid(node c,node a,node b)
{
    if(a.x!=b.x)
    {
        if(abs(a.x-b.x)>abs(a.x-c.x)) return 1;
    }else if(abs(a.y-b.y)>abs(a.y-c.y)) return 1;
    return 0;
}
void solve()
{
    int i,j,k,used[N][N];
    double ans=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            ans+=map1[i][j];
            used[i][j]=0;
        }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            for(k=1;k<=n;k++)
            {
            if(i==j || j==k || i==k) continue;
            if(calck(point[i],point[j])==calck(point[i],point[k]) && mid(point[k],point[i],point[j]) && used[i][k]==0 && used[k][i]==0)
                    {ans-=map1[i][k]*2;used[i][k]=1;}
            }
        }
    }
    ans/=2;
    cout<<(int)(ans)<<endl;
}
int main()
{
    init();
    solve();
    return 0;
}