oj.uz

답안 #942709

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
942709 2024-03-11T03:14:32 Z vjudge1 Nicelines (RMI20_nicelines) C++14
11 / 100
 39 ms 600 KB 
#include "nice_lines.h"

#include <bits/stdc++.h>

using namespace std;

template<class T>
struct Point{
   T x, y;
   Point (T _x=0, T _y=0){
      x=_x; y=_y;
   }
   bool operator<(Point a){ return tie(x, y)<tie(a.x, a.y); }
   bool operator==(Point a){ return tie(x, y)==tie(a.x, a.y); }
   Point operator+(Point a){ return Point(x+a.x, y+a.y); }
   Point operator-(Point a){ return Point(x-a.x, y-a.y); }
   Point operator*(T a){ return Point(x*a, y*a); }
   Point operator/(T a){ return Point(x/a, y/a); }
   T dot(Point a){ return x*a.x+y*a.y; }
   T dot(Point a, Point b){ return (a-*this).dot(b-*this); }
   T cross(Point a){ return x*a.y-y*a.x; }
   T cross(Point a, Point b){ return (a-*this).cross(b-*this); }
   T dist2(){ return x*x+y*y; }
   long double dist(){ return sqrt(dist2()); }
};

using pt=Point<long double>;

long double line_point_dist(pt a, pt b, pt c){
   return abs(a.cross(b, c))/(a-b).dist();
}

mt19937 rng(69420);

long double rand(long double l, long double r){
   return uniform_real_distribution<long double>(l, r)(rng);
}

void solve(int subtask_id, int N) {
   if (N==1){
      pt a, b;
      {
         pt l(-1e12, -rand(0, 69420));
         pt r(1e12, rand(0, 69420));
         for (int i=0; i<1000; ++i){
            pt m1=l+(r-l)/3, m2=l+(r-l)/3*2;
            long double t1=query(m1.x, m1.y), t2=query(m2.x, m2.y);
            if (t1<t2) r=m2;
            else l=m1;
         }
         a=l;
      }
      {
         pt l(-rand(0, 69420), -1e12);
         pt r(rand(0, 69420), 1e12);
         for (int i=0; i<1000; ++i){
            pt m1=l+(r-l)/3, m2=l+(r-l)/3*2;
            long double t1=query(m1.x, m1.y), t2=query(m2.x, m2.y);
            if (t1<t2) r=m2;
            else l=m1;
         }
         b=l;
      }
      long double slope=round((b.y-a.y)/(b.x-a.x));
      cerr << fixed << setprecision(6) << a.x << ' ' << a.y << ' ' << b.x << ' ' << b.y << endl;
      the_lines_are({(int)(round(slope))}, {(int)(round(a.y-a.x*slope))});
      return;
   }
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 440 KB Output is correct
2 Correct 32 ms 440 KB Output is correct
3 Correct 39 ms 600 KB Output is correct
4 Correct 35 ms 436 KB Output is correct

Subtask #2
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -