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

Обсуждение задачи 1726. Кто ходит в гости…

What 's on Test 2? Help me plz
Послано quangduytr 22 фев 2017 07:54
#include <bits/stdc++.h>

using namespace std;
struct duy{
    long long x,y;
};
duy a[100005];
bool cmp1(duy a, duy b){
    return a.x>b.x;
}
bool cmp2(duy a, duy b){
    return a.y>b.y;
}
long long n,dem=0,t=-99,s[100005][2],duoi[100005],res=0;
double q;
int main()
{
    cin>>n;
    for(long long i=1; i<=n; i++) cin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,cmp1);
    for(long long i=1; i<=n; i++){
        if(a[i].x==t) s[dem][2]++;
        else{
            dem++;
            s[dem][1]=a[i].x;
            s[dem][2]=1;
            t=a[i].x;
        }
    }
    duoi[dem]=0;
    for(long long i=dem-1; i>=1; i--) duoi[i]=duoi[i+1]+s[i+1][2];
    for(long long i=1; i<=dem-1; i++) res=res+s[i][2]*duoi[i]*(s[i][1]-s[i+1][1]);
    sort(a+1,a+n+1,cmp2);
    dem=0;
    for(long long i=1; i<=n; i++){
        if(a[i].y==t) s[dem][2]++;
        else{
            dem++;
            s[dem][1]=a[i].y;
            s[dem][2]=1;
            t=a[i].y;
        }
    }
    duoi[dem]=0;
    for(long long i=dem-1; i>=1; i--) duoi[i]=duoi[i+1]+s[i+1][2];
    for(long long i=1; i<=dem-1; i++) res=res+s[i][2]*duoi[i]*(s[i][1]-s[i+1][1]);
    q=((double)((double)2*(double)res))/((double)((double)n*(double)(n-1)));
    cout<<roundf(q*1)/1;
}