QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#54586	#55. 欧几里得距离之和	KuriyamaMirai^#	0	30ms	6560kb	C++14	11.4kb	2022-10-09 19:42:50	2022-10-09 19:42:51

Judging History

你现在查看的是最新测评结果

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-10-09 19:42:51]
评测

测评结果：0
用时：30ms
内存：6560kb

查看

[2022-10-09 19:42:50]
提交

answer

/**
 * @file 55.cpp
 * @author Kuriyama Mirai ([email protected])
 * @brief 
 * @date 2022-10-09
 * 
 * @copyright Copyright (c) 2022
 * 
 */
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <cmath>

namespace mirai {
#define FILE_IO
#ifdef FILE_IO
#define MIRAI_INPUT_BUFFER
#endif
#define MIRAI_INPUT_BUFFER_SIZE (1L << 16)
#define MIRAI_USE_ARG_LIST

#define ll long long
#define u unsigned
void flush_input(); ll sscan(); void sread(bool&); void sread(int&); void sread(u&); void sread(short&); 
void sread(long&); void sread(ll&); void sread(u short&); void sread(u long&); void sread(u ll&); void sread(char&); 
void sread(char*); void sread(float&); void sread(double&); void sread(long double&); template <typename type> 
void sread(type&); u ll scan(); void read(bool&); void read(int&); void read(short&); void read(long&); void read(ll&); 
void read(u int&); void read(u short&); void read(u long&); void read(u ll&); void read(char&); void read(char*); 
void read(float&); void read(double&); void read(long double&); template <typename type> void read(type&); char readch(); 
char readc(); void readstr(char*); float readf(); double readdf(); long double readlf();
#if (defined(MIRAI_USE_ARG_LIST) && __cplusplus >= 201103L) || defined(MIRAI_FORCE_USE_ARG_LIST)
template <typename type, typename... Args> void sread(type&, Args&...); 
template <typename type, typename... Args> void read(type&, Args&...); 
#endif
#undef u
#undef ll
}  // namespace mirai

#define MIRAI_TESTNO "55-2"

namespace mirai {

using db = double;
constexpr int MAXN = 5.5e5;
constexpr db PI = 2 * std::acos(0);
db x[MAXN], y[MAXN], t[MAXN];

int main() {
  int n = scan();
  for (int i = 1; i <= n; ++i) {
    x[i] = sscan();
    y[i] = sscan();
  }
  int m = 200;
  db ans = 0;
  for (int i = 0; i < m; ++i) {
    db th = (i + .5) * 2 * PI / m;
    db cos = std::cos(th), sin = std::sin(th);
    for (int i = 1; i <= n; ++i) {
      t[i] = x[i] * cos + y[i] * sin;
    }
    std::sort(t + 1, t + n + 1);
    db sum = 0, res = 0;
    for (int i = 1; i <= n; ++i) {
      sum += t[i];
      res += static_cast<db>(i) * t[i] - sum;
    }
    ans += res;
  }
  std::printf("%.10lf\n", ans / (m + 1) / 2 * PI);
  return 0;
}

}  // namespace mirai

namespace mirai {

#if !defined(MIRAI_FORCE_USE_ARG_LIST) && defined(MIRAI_USE_ARG_LIST) && \
  __cplusplus < 201103L
#error MIRAI_USE_ARG_LIST needs C++11 to enable. \
use MIRAI_FORCE_USE_ARG_LIST if really need.
#endif
#ifdef MIRAI_FORCE_USE_ARG_LIST
#define MIRAI_USE_ARG_LIST
#endif

#if !defined(MIRAI_FORCE_ATTR_EXPECT) && defined(MIRAI_ATTR_EXPECT) && \
  __cplusplus < 202002L
#error MIRAI_ATTR_EXPECT needs C++20 to enable. \
use MIRAI_FORCE_ATTR_EXPECT if really need.
#undef MIRAI_ATTR_EXPECT
#endif
#ifdef MIRAI_FORCE_ATTR_EXPECT
#define MIRAI_ATTR_EXPECT
#endif

#ifdef MIRAI_ATTR_EXPECT
#define ift(x) [[likely]] if (x)
#define iff(x) [[unlikely]] if (x)
#define whilet(x) [[unlikely]] while (x)
#define whilef(x) [[likely]] while (x)
#elif defined(MIRAI_BUILTIN_EXPECT)
#define ift(x) if (__builtin_expect(!!(x), 1))
#define iff(x) if (__builtin_expect(!!(x), 0))
#define whilet(x) while (__builtin_expect(!!(x), 1))
#define whilef(x) while (__builtin_expect(!!(x), 0))
#else 
#define ift(x) if (x)
#define iff(x) if (x)
#define whilet(x) while (x)
#define whilef(x) while (x)
#endif

#ifndef MIRAI_INPUT_BUFFER_SIZE
#define MIRAI_INPUT_BUFFER_SIZE (1UL << 16)
#endif
#ifndef MIRAI_OUTPUT_BUFFER_SIZE
#define MIRAI_OUTPUT_BUFFER_SIZE (1UL << 16)
#endif

#ifdef MIRAI_INPUT_BUFFER
// let *input_buffer_end = '\0'.
char input_buffer[MIRAI_INPUT_BUFFER_SIZE + 1];
char *input_buffer_now = input_buffer;
char *input_buffer_end = input_buffer + MIRAI_INPUT_BUFFER_SIZE;

void flush_input(void) {
  #ifdef MIRAI_USE_READ_FUNC
  std::size_t ret = ::read(0, input_buffer, MIRAI_INPUT_BUFFER_SIZE);
  #else
  std::size_t ret = std::fread(input_buffer, sizeof(input_buffer[0]), 
    MIRAI_INPUT_BUFFER_SIZE, stdin);
  #endif
  iff(ret < MIRAI_INPUT_BUFFER_SIZE) {
    input_buffer[ret] = '\0';
  }
  input_buffer_now = input_buffer;
  return;
}
#else
void flush_input(void) {}
#endif

#ifndef MIRAI_INPUT_BUFFER
#define readchar() (std::getchar())
#else
char readchar(void) {
  iff(input_buffer_now == input_buffer_end) {
    flush_input();
  }
  return *(input_buffer_now++);
}
#endif

#ifdef MIRAI_USE_ISDIGIT
#define digit(x) (std::isdigit(x))
#else
#define digit(x) ((x) >= '0' && (x) <= '9')
#endif

void readstr(char*);

long long sscan(void) {
  char ch = readchar();
  whilet(!digit(ch) && ch != '-') {
    ch = readchar();
  }
  unsigned long long ret = 0;
  bool flag = false;
  iff(ch != '-') {
    ret = ch - '0';
  } else {
    flag = true;
  }
  ch = readchar();
  whilet(digit(ch)) {
    ret = ret * 10 + ch - '0';
    ch = readchar();
  }
  iff(flag) {
    return -ret;
  } else {
    return ret;
  }
}

void sread(bool& u) { u = sscan(); }
void sread(int& u) { u = sscan(); }
void sread(short& u) { u = sscan(); }
void sread(long& u) { u = sscan(); }
void sread(long long& u) { u = sscan(); }
void sread(unsigned int& u) { u = sscan(); }
void sread(unsigned short& u) { u = sscan(); }
void sread(unsigned long& u) { u = sscan(); }
void sread(unsigned long long& u) { u = sscan(); }

void sread(char& u) {
  u = readchar();
  return;
}
void sread(char* str) {
  readstr(str);
  return;
}

void sread(float& u) { u = readf(); }
void sread(double& u) { u = readdf(); }
void sread(long double& u) { u = readlf(); }

#ifdef MIRAI_USE_ARG_LIST
// Very SLOW.
template <typename type, typename... Args>
void sread(type &u, Args&... args) {
  sread(u);
  sread(args...);
  return;
}
#endif

// ignores character '-'.
unsigned long long scan(void) {
  char ch = readchar();
  whilet(!digit(ch)) {
    ch = readchar();
  }
  unsigned long long ret = ch - '0';
  ch = readchar();
  whilet(digit(ch)) {
    ret = ret * 10 + ch - '0';
    ch = readchar();
  }
  return ret;
}

void read(bool& u) { u = scan(); }
void read(int& u) { u = scan(); }
void read(short& u) { u = scan(); }
void read(long& u) { u = scan(); }
void read(long long& u) { u = scan(); }
void read(unsigned int& u) { u = scan(); }
void read(unsigned short& u) { u = scan(); }
void read(unsigned long& u) { u = scan(); }
void read(unsigned long long& u) { u = scan(); }

void read(char& u) {
  u = readchar();
}
void read(char* str) {
  readstr(str);
  return;
}

void read(float& u) { u = readf(); }
void read(double& u) { u = readdf(); }
void read(long double& u) { u = readlf(); }

#ifdef MIRAI_USE_ARG_LIST
// Very SLOW.
template <typename type, typename... Args>
void read(type &u, Args&... args) {
  read(u);
  read(args...);
  return;
}
#endif

bool isvisible(char ch) {
  return ch > '\x20' && ch < '\x7F';
}

char readch(void) {
  char ch;
  ch = readchar();
  return ch;
}
char readc(void) {
  char ch;
  ch = readchar();
  whilet(!isvisible(ch)) {
    ch = readchar();
  }
  return ch;
}

void readstr(char* str) {
  *str = ' ';
  whilef(!isvisible(*str)) {
    *str = readchar();
  }
  whilet(isvisible(*str)) {
    str++;
    *str = readchar();
  }
  *str = '\0';
  return;
}

float readf(void) {
  float x = 0;
  char ch = readchar();
  whilet(!digit(ch) && ch != '-') {
    ch = readchar();
  }
  bool flag = false;
  iff(ch == '-') {
    flag = true;
  } else iff(ch != '+' && ch != '.') {
    x = ch - '0';
  }
  ch = readchar();
  whilet(digit(ch)) {
    x = x * 10 + ch - '0';
    ch = readchar();
  }
  ift(ch == '.') {
    float tmp = 0;
    tmp = 0.1;
    ch = readchar();
    whilet(digit(ch)) {
      x += tmp * (ch - '0');
      tmp = tmp * 0.1;
      ch = readchar();
    }
  }
  ift(ch == 'e' || ch == 'E') {
    unsigned int y = 0, cnt = 6;
    ch = readchar();
    bool flag2 = false;
    iff(ch == '-') {
      flag2 = true;
    } else ift(digit(ch)) {
      y = ch - '0';
      cnt--;
    }
    ch = readchar();
    whilet(digit(ch) && cnt) {
      y = y * 10 + (ch - '0');
      cnt--;
      ch = readchar();
    }
    if (digit(ch) && cnt == 0) {
      while (digit(ch)) {
        ch = readchar();
      }
    }
    if (flag2) {
      x = x * std::pow(10.F, -1.F * y);
    } else {
      x = x * std::pow<float, float>(10, y);
    }
  }
  iff(flag) {
    return -x;
  } else {
    return x;
  }
}
double readdf(void) {
  double x = 0;
  char ch = readchar();
  whilet(!digit(ch) && ch != '-') {
    ch = readchar();
  }
  bool flag = false;
  iff(ch == '-') {
    flag = true;
  } else iff(ch != '+' && ch != '.') {
    x = ch - '0';
  }
  ch = readchar();
  whilet(digit(ch)) {
    x = x * 10 + ch - '0';
    ch = readchar();
  }
  ift(ch == '.') {
    double tmp = 0;
    tmp = 0.1;
    ch = readchar();
    whilet(digit(ch)) {
      x += tmp * (ch - '0');
      tmp = tmp * 0.1;
      ch = readchar();
    }
  }
  ift(ch == 'e' || ch == 'E') {
    unsigned int y = 0, cnt = 6;
    ch = readchar();
    bool flag2 = false;
    iff(ch == '-') {
      flag2 = true;
    } else ift(digit(ch)) {
      y = ch - '0';
      cnt--;
    }
    ch = readchar();
    whilet(digit(ch) && cnt) {
      y = y * 10 + (ch - '0');
      cnt--;
      ch = readchar();
    }
    if (digit(ch) && cnt == 0) {
      while (digit(ch)) {
        ch = readchar();
      }
    }
    if (flag2) {
      x = x * std::pow(10., -1. * y);
    } else {
      x = x * std::pow<double, double>(10, y);
    }
  }
  iff(flag) {
    return -x;
  } else {
    return x;
  }
}
long double readlf(void) {
  long double x = 0;
  char ch = readchar();
  whilet(!digit(ch) && ch != '-') {
    ch = readchar();
  }
  bool flag = false;
  iff(ch == '-') {
    flag = true;
  } else iff(ch != '+' && ch != '.') {
    x = ch - '0';
  }
  ch = readchar();
  whilet(digit(ch)) {
    x = x * 10 + ch - '0';
    ch = readchar();
  }
  ift(ch == '.') {
    long double tmp = 0;
    tmp = 0.1;
    ch = readchar();
    whilet(digit(ch)) {
      x += tmp * (ch - '0');
      tmp = tmp * 0.1;
      ch = readchar();
    }
  }
  ift(ch == 'e' || ch == 'E') {
    unsigned int y = 0, cnt = 6;
    ch = readchar();
    bool flag2 = false;
    iff(ch == '-') {
      flag2 = true;
    } else ift(digit(ch)) {
      y = ch - '0';
      cnt--;
    }
    ch = readchar();
    whilet(digit(ch) && cnt) {
      y = y * 10 + (ch - '0');
      cnt--;
      ch = readchar();
    }
    if (digit(ch) && cnt == 0) {
      while (digit(ch)) {
        ch = readchar();
      }
    }
    if (flag2) {
      x = x * std::pow(10.L, -1.L * y);
    } else {
      x = x * std::pow<long double, long double>(10, y);
    }
  }
  iff(flag) {
    return -x;
  } else {
    return x;
  }
}

#undef ift
#undef iff
#undef whilet
#undef whilef
#undef digit
#undef readchar

}  // namespace mirai

int main() {
  #if defined(MIRAI_LOCAL) && defined(FILE_IO)
  std::freopen(__FILE__ "\\..\\tests\\" MIRAI_TESTNO ".in", "r", stdin);
  std::freopen(__FILE__ "\\..\\tests\\" MIRAI_TESTNO ".out", "w", stdout);
  #endif
  #ifdef MIRAI_INPUT_BUFFER
  mirai::flush_input();
  #endif
  int ret = mirai::main();
  #if defined(MIRAI_LOCAL) && defined(FILE_IO)
  std::fclose(stdin);
  std::fclose(stdout);
  #endif
  return ret;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 0

Wrong Answer

time: 30ms

memory: 6560kb

input:

3000
-802420 -321989
227507 956314
-460698 -819834
-479809 -341770
191520 109304
712327 -189558
-578326 -41090
282566 982266
-859119 686756
209058 -23298
-884994 -349898
-11358 182915
-507706 -81622
745434 575941
-374809 139274
810223 367608
960234 -197223
439081 573568
-275182 999306
-583036 -61808...

output:

4669799800078.2822265625

result:

wrong answer 1st numbers differ - expected: '4693148621177.00000', found: '4669799800078.28223', error = '0.00498'

Subtask #2:

score: 0

Skipped

Dependency #1:

Subtask #3:

score: 0

Skipped

Dependency #1:

Subtask #4:

score: 0

Skipped

Dependency #1:

Subtask #5:

score: 0

Skipped