oj.uz

답안 #647099

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
647099 2022-10-01T15:01:27 Z danikoynov Nicelines (RMI20_nicelines) C++14
100 / 100
 12 ms 336 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'
#include "nice_lines.h"
using namespace std;
typedef long long ll;


using namespace std;
typedef long long ll;

int V = 1e4 + 10;
const long double eps = 1e-4;

struct point
{
    long double x, y;

    point(long double _x = 0, long double _y = 0)
    {
        x = _x;
        y = _y;
    }
};

struct line
{
    point A, B;
    long double k, m;

    line(point _A, point _B)
    {
        A = _A;
        B = _B;
        k = (B.y - A.y) / (B.x - A.x);
        /// k * A.x + m = A.y
        m = A.y - A.x * k;
    }

    bool operator < (const line &l) const
    {
        return k < l.k;
    }
};


point intersection(line l1, line l2)
{
    long double x = (l2.m - l1.m) / (l1.k - l2.k), y = l1.k * x + l1.m;
    return point(x, y);
}

vector < line > cur;
long double cross(long double x)
{
    for (int a = -V; a <= V; a ++)
    {
        long double lf = x - (long double)(3 * V * a);
        if (abs(lf) <= V)
            return a;
    }
    return 1e9;
}

bool same(line l1, line l2)
{
    ///cout << abs(l1.k - l2.k) << " " << abs(l1.m - l2.m) << endl;
    if (abs(l1.k - l2.k) < eps)
        return true;
    return false;
}

int _N;
void divide(line l1, line l2)
{
    if (cur.size() == _N + 1)
        return;
    ///cout << l1.k << " " << l1.m << " " << l2.k << " " << l2.m << endl;
    point p = intersection(l1, l2);
    long double cr = cross(p.x);
    if (cr == 1e9)
    {
        point p1(p.x, query(3 * V, p.x));
        point p2(p.x + 1, query(3 * V, p.x + 1));
        line l3(p1, p2);
        cur.push_back(l3);
        divide(l1, l3);
        divide(l3, l2);
        return;
    }
    else
    {
        long double t1 = (long double)(3 * V) * cr - V - 1;
        long double t2 = (long double)(3 * V) * cr + V + 1;

        point p1(t1, query(3 * V, t1));
        line l3(p1, p);
        /**cout << l3.k << " " << l3.m << endl;
        cout << l1.k << " " << l1.m << endl;
         cout << t1 << " " << t2 << endl;*/

         ///cout << l1.k << " " << l3.k << endl;
        if (!same(l1, l3))
        {
            ///exit(0);
            point df(t1 + 1, query(3 * V, t1 + 1));
            line dl(p1, df);
            cur.push_back(dl);
            divide(l1, dl);
            divide(dl, l2);
            return;
        }
    ///cout << "here" << endl;        exit(0);
        point p2(t2, query(3 * V, t2));
        line l4(p, p2);
        if (!same(l2, l4))
        {
            point df(t2 - 1, query(3 * V, t2 - 1));
            line dl(df, p2);
            cur.push_back(dl);
            divide(l1, dl);
            divide(dl, l2);
            return;
        }
    }
}
void solve(int subtask_id, int N)
{

    if (subtask_id == 4)
        V = 510;
    _N = N;
    point A1(3 * V * V, query(3 * V, 3 * V * V)), B1(3 * V * V + 1, query(3 * V, 3 * V * V + 1));
    line l1(A1, B1);
    point A2(- 3 * V * V, query(3 * V, - 3 * V * V)), B2(- 3 * V * V + 1, query(3 * V, - 3 * V * V + 1));
    line l2(A2, B2);

    cur.push_back(l1);
    cur.push_back(l2);

    divide(l2, l1);


    vector < long double > it;
    sort(cur.begin(), cur.end());
    for (int i = 1; i < cur.size(); i ++)
    {
        it.push_back(intersection(cur[i - 1], cur[i]).x);
    }


    vector < int > a;
    vector < int > b;
    for (int i = 0; i < it.size(); i ++)
    {
        for (int pa = -V; pa <= V; pa ++)
        {
            long double lf = it[i] - (long double)(3 * V * pa);
            if (abs(lf) <= V)
            {
                a.push_back(pa);
                b.push_back(round(lf));
                break;
            }
        }
    }

    the_lines_are(a, b);
}

Compilation message

nicelines.cpp: In function 'void divide(line, line)':
nicelines.cpp:83:20: warning: comparison of integer expressions of different signedness: 'std::vector<line>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |     if (cur.size() == _N + 1)
      |         ~~~~~~~~~~~^~~~~~~~~
nicelines.cpp: In function 'void solve(int, int)':
nicelines.cpp:153:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |     for (int i = 1; i < cur.size(); i ++)
      |                     ~~^~~~~~~~~~~~
nicelines.cpp:161:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |     for (int i = 0; i < it.size(); i ++)
      |                     ~~^~~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 328 KB Output is correct
2 Correct 6 ms 336 KB Output is correct
3 Correct 8 ms 332 KB Output is correct
4 Correct 5 ms 332 KB Output is correct

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 208 KB Output is correct
2 Correct 5 ms 208 KB Output is correct
3 Correct 6 ms 316 KB Output is correct
4 Correct 3 ms 308 KB Output is correct

Subtask #6
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 328 KB Output is correct
2 Correct 6 ms 336 KB Output is correct
3 Correct 8 ms 332 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 4 ms 208 KB Output is correct
6 Correct 5 ms 208 KB Output is correct
7 Correct 6 ms 316 KB Output is correct
8 Correct 3 ms 308 KB Output is correct
9 Correct 12 ms 336 KB Output is correct
10 Correct 10 ms 316 KB Output is correct
11 Correct 11 ms 336 KB Output is correct
12 Correct 11 ms 328 KB Output is correct