Submission #647097

#	Time	Username	Problem	Language	Result	Execution time	Memory
647097		danikoynov	Nicelines (RMI20_nicelines)	C++14	99.99 / 100	14 ms	448 KiB

nicelines

/**
 ____ ____ ____ ____ ____ ____
||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 (stderr)

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 ++)
      |                     ~~^~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 18.995842883599998 / 19
• Subtask 5: 23 / 23
• Subtask 6: 26.9940925188 / 27