제출 #218763

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
218763		gratus907	먼 별 (KOI16_dist)	C++17	81 / 100	972 ms	4472 KiB

dist

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(x) ((x).begin()),((x).end())
#define int ll
using pii = pair <int, int>;
#define INF 0x7f7f7f7f7f7f7f7f
const bool debug = 0;
struct point
{
    int x, y, dx, dy;
    point operator+(const point &other)
    {
        return {x+other.x, y+other.y};
    }
    point operator-(const point &other)
    {
        return {x-other.x, y-other.y};
    }
    point operator*(const int C)
    {
        return {x*C, y*C, dx, dy};
    }
    int normsq()
    {
        return x*x+y*y;
    }
};

int dist(point &a, point &b)
{
    return (a-b).normsq();
}
class convex_hull
{
public:
    int n;
    static int ccw (point &a, point &b, point &c)
    {
        int v = (b.x - a.x) * (c.y - a.y) - (b.y-a.y)*(c.x-a.x);
        if (v > 0) return 1;
        if (!v) return 0;
        return -1;
    }
    static bool compy (point &a, point &b)
    {
        if (a.y == b.y) return a.x < b.x;
        return a.y < b.y;
    }
    vector <point> pt;
    vector <point> convex;
    void graham_scan()
    {
        convex.clear();
        sort(all(pt), compy);
        point down = pt[0];
        sort(all(pt), [&down](auto a, auto b)
        {
            int u = ccw(down, a, b);
            if (u!=0) return u>0;
            else return dist(down, a) < dist(down, b);
        });
        convex.push_back(pt[0]);
        convex.push_back(pt[1]);
        for (int i = 2; i<n; i++)
        {
            while(convex.size() > 1)
            {
                point tp = convex.back();
                convex.pop_back();
                point tptp = convex.back();
                if (ccw(tptp,tp,pt[i]) > 0)
                {
                    convex.push_back(tp);
                    break;
                }
            }
            convex.push_back(pt[i]);
        }
    }
    int rotating_calipers()
    {
        int msz = 0;
        int t = 0;
        point o = {0, 0};
        int nc = convex.size();
        for (int i = 0, j = 1; i<nc; i++)
        {
            while (ccw(o, convex[i%nc], convex[j%nc]) > 0) j++;
            for (int k = j; k < j+2; k++)
            {
                int d = dist(convex[i%nc], convex[k%nc]);
                if (d > msz)
                    msz = d;
            }
        }
        return msz;
    }
};

convex_hull C;
vector <point> ptt;
int n, t;
int func(int x)
{
    C.pt.clear();
    for (int i = 0; i<n; i++)
        C.pt.push_back({ptt[i].x+ptt[i].dx*x, ptt[i].y+ptt[i].dy*x,0,0});
    C.graham_scan();
    if (debug)
    {
        printf("Time %lld information\n", x);
        for (auto it:C.convex)
            printf("%lld %lld\n",it.x, it.y);
    }
    int u = C.rotating_calipers();
    if (debug)
    {
        printf("Time %lld : Best dist %lld\n",x, u);
        printf("\n");
    }
    return u;
}
int32_t main()
{
    usecppio
    cin >> n >> t;
    C.n = n;
    for (int i = 0; i<n; i++)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        ptt.push_back({a, b, c, d});
    }
    int lo = 0, hi = t;
    while(lo + 3 < hi)
    {
        int m1 = (2*lo+hi)/3;
        int m2 = (lo+2*hi)/3;
        if (func(m1) > func(m2))
            lo = m1;
        else hi = m2;
    }
    int ind = lo;
    int best = func(lo);
    for (int i = lo; i<=hi; i++)
    {
        int cur = func(i);
        if (cur < best)
        {
            best = cur;
            ind = i;
        }
    }
    cout << ind << '\n';
    cout << best << '\n';
}

컴파일 시 표준 에러 (stderr) 메시지

dist.cpp: In member function 'long long int convex_hull::rotating_calipers()':
dist.cpp:89:13: warning: unused variable 't' [-Wunused-variable]
         int t = 0;
             ^

• Subtask 1: 2 / 2
• Subtask 2: 40 / 40
• Subtask 3: 39 / 39
• Subtask 4: 0 / 19