oj.uz

답안 #1095646

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1095646 2024-10-02T19:04:59 Z MrPavlito Fence (CEOI08_fence) C++17
40 / 100
 1 ms 600 KB 
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define endl "\n"
#define pii pair<int,int>

using namespace std;

const int MAXN = 105;
const int mod7 = 1e9+7;
const long long inf = 1e18;
int n,m;
vector<pii> polygon;
set<pii> deopolygona;
vector<vector<int>> graf(MAXN);
vector<bool> visited(MAXN);
vector<int> dist(MAXN);
int finalscore = 0;


int orientation(pii a, pii b, pii c)
{
    double v = a.fi*(b.sc-c.sc) + b.fi*(c.sc-a.sc) + c.fi*(a.sc-b.sc);
    if(v<0)return -1;
    if(v>0)return 1;
    return 0;
}

int kvadrat(int broj)
{
    return broj*broj;
}

bool isclockwise(pii a, pii b, pii c)
{
    int o = orientation(a,b,c);
    return o<0;
}

bool isColinear(pii a, pii b, pii c)
{
    return orientation(a,b,c) == 0;
}



void convexHull(vector<pii>& bandere)
{
    pii p0 = {inf, inf};
    for(int i=0; i<n; i++)
    {
        if(p0.sc > bandere[i].sc)p0 = bandere[i];
        else if(p0.sc == bandere[i].sc && p0.fi > bandere[i].fi)p0 = bandere[i];
    }
    sort(bandere.begin(), bandere.end(), [&p0](const pii& a, const pii& b) {
        int o = orientation(p0, a, b);
        if (o == 0)
            return kvadrat(p0.fi - a.fi) + kvadrat(p0.sc-a.sc)<  kvadrat(p0.fi - b.fi) + kvadrat(p0.sc-b.sc);
        return o < 0;
    });

    for(int i=0; i<n; i++)
    {
        while(polygon.size()>1 && !isclockwise(polygon[polygon.size()-2], polygon.back(), bandere[i]))polygon.pop_back();
        polygon.pb(bandere[i]);
    }
    for(auto x: polygon)deopolygona.insert(x);
}

void bfs(int nod)
{
    queue<pii> q;
    for(auto x: graf[nod])q.push({x, 1});
    while(!q.empty())
    {
        auto tr = q.front();
        q.pop();
        if(visited[tr.fi])continue;
        visited[tr.fi] = 1;
        dist[tr.fi] = tr.sc;
        for(auto x: graf[tr.fi])
        {
            if(!visited[x])q.push({x, tr.sc+1});
        }
    }
}



signed main()
{
    ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
    int tt=1;
    //cin >> tt;
    while(tt--)
    {
        cin >> n >> m;
        vector<pii> bandere(n);
        vector<pii> drveca(m);
        vector<pii> availabledrvece;
        vector<pii> availablebandere;
        for(int i=0; i<n; i++)cin >> bandere[i].fi >> bandere[i].sc;
        for(int i=0; i<m; i++)cin >> drveca[i].fi >> drveca[i].sc;
        convexHull(bandere);
        for(int i=0; i<m; i++)
        {
            bool jesteunutra = true;
            for(int j=0; j<(int)polygon.size(); j++)
            {
                int o = orientation(polygon[j], polygon[(j+1)%(int)polygon.size()], drveca[i]);
                if(o != -1)
                {
                    jesteunutra = false;
                    break;
                }
            }
            if(jesteunutra)availabledrvece.pb(drveca[i]);
        }
        if(availabledrvece.size() == 0)
        {
            cout << m*111 << endl;
            return 0;
        }
        finalscore += (m - (int)availabledrvece.size())*111;
        for(int i=0; i<n; i++)
        {
            if(deopolygona.count(bandere[i]))continue;
            bool jesteunutra = true;
            for(int j=0; j<(int)polygon.size(); j++)
            {
                int o = orientation(polygon[j], polygon[(j+1)%(int)polygon.size()], bandere[i]);
                if(o != -1)
                {
                    jesteunutra = false;
                    break;
                }
            }
            if(jesteunutra)availablebandere.pb(drveca[i]);
        }
        for(auto x: polygon)availablebandere.pb(x);
        int N = (int)availablebandere.size();
        for(int i=0; i<N-1; i++)
        {
            for(int j = i+1; j<N; j++)
            {
                pii a= availablebandere[i];
                pii b= availablebandere[j];
                bool moze = true;
                for(auto x: availabledrvece)
                {
                    int o = orientation(a,b,x);
                    if(o != -1)
                    {
                        moze = 0;
                        break;
                    }
                }
                if(moze)graf[i].pb(j);
                moze = true;
                for(auto x: availabledrvece)
                {
                    int o = orientation(b,a,x);
                    if(o != -1)
                    {
                        moze = 0;
                        break;
                    }
                }
                if(moze)graf[j].pb(i);

            }
        }
        int rez = inf;
        for(int i=0; i<N; i++)
        {
            fill(all(dist), inf);
            fill(all(visited), 0);
            bfs(i);
            rez = min(rez, dist[i]);
        }
        cout << finalscore + rez*20 << endl;



    }
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 452 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -