글 읽기 - double은 맞고 int는 틀립니다.

hayman42 1년 전 1

실수 오차를 감안하여 모든 입력에 1000을 곱하였습니다. 그에 따라 V*S에도 100만을 곱했습니다. 그런데 계속 틀렸다길래 double로 바꿔보니 맞다고 나오네요.. 혹시 문자열 처리 과정에서 어떤 문제가 있는걸까요? 아니면 double은 맞고 int는 틀린 데이터가 있는걸까요? 그런 경우가 있다면 데이터의 수정이 필요해 보입니다.

#include <bits/stdc++.h>
using namespace std;

#define all(v) (v).begin(), (v).end()
typedef long long ll;
typedef unsigned long long ull;

int N, M, mouse[100][2], hole[100][2], cap[202][202], flow[202][202];
bool check[202];
ll S, V;
vector<int> adj[202];

int to_int(string s);
ll dst(int n, int m);
int maxflow();
bool dfs(int cur);

int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    int i, j, k, a, b;
    string n, m;
    cin >> N >> M >> S >> V;
    for (i = 0; i < N; i++)
    {
        adj[0].push_back(i + 1);
        adj[i + 1].push_back(0);
        cap[0][i + 1] = 1;
        cin >> n >> m;
        mouse[i][0] = to_int(n);
        mouse[i][1] = to_int(m);
    }
    for (i = 0; i < M; i++)
    {
        adj[N + 1 + i].push_back(N + M + 1);
        adj[N + M + 1].push_back(N + 1 + i);
        cap[N + 1 + i][N + M + 1] = 1;
        cin >> n >> m;
        hole[i][0] = to_int(n);
        hole[i][1] = to_int(m);
    }
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < M; j++)
        {
            ll d = dst(i, j);
            if (d <= V * V * S * S * 1000000)
            {
                adj[i + 1].push_back(N + j + 1);
                adj[N + j + 1].push_back(i + 1);
                cap[i + 1][N + j + 1] = 1;
            }
        }
    }
    cout << N - maxflow();
    return 0;
}

int to_int(string s)
{
    int i, res = 0, pos, digit;
    for (i = 0; i < s.length(); i++)
    {
        if (s[i] == '.')
        {
            pos = i;
            break;
        }
    }
    for (i = pos - 1, digit = 1000; s[i] != '-' && i >= 0; i--, digit *= 10)
        res += digit * (s[i] - '0');
    for (i = pos + 1, digit = 100; i < s.length(); i++, digit /= 10)
        res += digit * (s[i] - '0');
    if (s[0] == '-')
        res = -res;
    return res;
}

ll dst(int n, int m)
{
    auto [a, b] = mouse[n];
    auto [c, d] = hole[m];
    return (a - c) * (ll)(a - c) + (b - d) * (ll)(b - d);
}

int maxflow()
{
    int ans, i, j, cur;
    for (ans = 0;; ans++)
    {
        fill(check, check + 202, false);
        if (!dfs(0))
            break;
    }
    return ans;
}

bool dfs(int cur)
{
    if (cur == N + M + 1)
        return true;
    check[cur] = true;
    for (auto itr : adj[cur])
    {
        if (check[itr] || cap[cur][itr] == flow[cur][itr])
            continue;
        flow[cur][itr]++, flow[itr][cur]--;
        if (dfs(itr))
            return true;
        flow[cur][itr]--, flow[itr][cur]++;
    }
    return false;
}

hijkl2e 7달 전 0

늦은 답변이지만 정수 자료형으로 풀립니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

double은 맞고 int는 틀립니다.

hayman42 1년 전 1

hijkl2e 7달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말