글 읽기 - 로직은 해답이랑 같은거 같은데

akswnd98 1년 전 0

틀렸습니다 뜹니다.

요즘 맞왜틀이 많네요.

반례 부탁드립니다.

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

typedef long long int64;

int64 N;

class Cut {
public:
  pair<int64, int64> s;
  pair<int64, int64> e;
  int64 w;
};

Cut cuts[2505];

bool compare_cut (const Cut &a, const Cut &b) {
  return a.w < b.w;
}

int64 cross_2d (const pair<int64, int64> &a, const pair<int64, int64> &b) {
  return a.first * b.second - a.second * b.first;
}

bool check_split (const Cut &a, const Cut &b) {
  const pair<int64, int64> spliter = make_pair(a.e.first - a.s.first, a.e.second - a.s.second);
  const pair<int64, int64> C = make_pair(b.s.first - a.s.first, b.s.second - a.s.second);
  const pair<int64, int64> CC = make_pair(b.e.first - a.s.first, b.e.second - a.s.second);
  return cross_2d(spliter, C) * cross_2d(spliter, CC) < 0;
}

bool check_cross (const Cut &a, const Cut &b) {
  return check_split(a, b) && check_split(b, a);
}

int main () {
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);

  cin >> N;
  for (int64 i = 0; i < N; i++) {
    cin >> cuts[i].s.first >> cuts[i].s.second >> cuts[i].e.first >> cuts[i].e.second >> cuts[i].w;
  }

  stable_sort(cuts, cuts + N, compare_cut);

  int64 rst = 0;
  for (int64 i = 0; i < N - 1; i++) {
    int64 cross_num = 1;
    for (int64 j = i + 1; j < N; j++) {
      cross_num += check_cross(cuts[i], cuts[j]) ? 1 : 0;
    }
    rst += cross_num * cuts[i].w;
  }
  rst += cuts[N - 1].w;

  cout << rst << '\n';

  return 0;
}

webh4ck 1년 전 3

overflow가 날 수 있어서 그런거 같네요

bool check_split (const Cut &a, const Cut &b) {
  const pair<int64, int64> spliter = make_pair(a.e.first - a.s.first, a.e.second - a.s.second);
  const pair<int64, int64> C = make_pair(b.s.first - a.s.first, b.s.second - a.s.second);
  const pair<int64, int64> CC = make_pair(b.e.first - a.s.first, b.e.second - a.s.second);
  return cross_2d(spliter, C) * cross_2d(spliter, CC) < 0; // overflow
}

akswnd98 1년 전 0

OMG!!!!

감사합니다 감사합니다 감사합니다 감사합니다.

kimcharless 1년 전 0

헉....범위 확인좀 진짜 잘해야겠네요

맞왜틀 시전하다가 이거보고 long long으로 바꿔서 해결했습니다...

진짜 난 바본가...ㅜ

감사합니다!!

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

문제

문제

출처

ICPC

로직은 해답이랑 같은거 같은데

akswnd98 1년 전 0

webh4ck 1년 전 3

akswnd98 1년 전 0

kimcharless 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말