답안 #647097

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
647097 2022-10-01T14:54:21 Z danikoynov Nicelines (RMI20_nicelines) C++14
99.9899 / 100
14 ms 448 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;


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;
}

void divide(line l1, line l2)
{
    ///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;
    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 solve(int, int)':
nicelines.cpp:146:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |     for (int i = 1; i < cur.size(); i ++)
      |                     ~~^~~~~~~~~~~~
nicelines.cpp:154:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |     for (int i = 0; i < it.size(); i ++)
      |                     ~~^~~~~~~~~~~
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 316 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
# 결과 실행 시간 메모리 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 2 ms 208 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Partially correct 6 ms 448 KB Output is partially correct
2 Partially correct 7 ms 328 KB Output is partially correct
3 Correct 9 ms 324 KB Output is correct
4 Partially correct 7 ms 208 KB Output is partially correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 208 KB Output is correct
2 Correct 4 ms 316 KB Output is correct
3 Correct 5 ms 208 KB Output is correct
4 Correct 4 ms 208 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Partially correct 6 ms 448 KB Output is partially correct
2 Partially correct 7 ms 328 KB Output is partially correct
3 Correct 9 ms 324 KB Output is correct
4 Partially correct 7 ms 208 KB Output is partially correct
5 Correct 5 ms 208 KB Output is correct
6 Correct 4 ms 316 KB Output is correct
7 Correct 5 ms 208 KB Output is correct
8 Correct 4 ms 208 KB Output is correct
9 Correct 12 ms 336 KB Output is correct
10 Correct 14 ms 328 KB Output is correct
11 Partially correct 12 ms 208 KB Output is partially correct
12 Correct 12 ms 312 KB Output is correct