質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

3回答

877閲覧

計算幾何学 / C++とPythonで同じことをやっても挙動が変わってしまう

kay_ventris4

総合スコア269

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

1クリップ

投稿2022/07/21 08:08

編集2022/07/21 23:02

問題

線分と線分の交差判定をする問題

Pythonの正解コード

Python

1def cross(x, y): 2 return x[0] * y[1] - x[1] * y[0] 3 4X1, Y1 = map(int, input().split()) 5X2, Y2 = map(int, input().split()) 6X3, Y3 = map(int, input().split()) 7X4, Y4 = map(int, input().split()) 8 9AB = [X2 - X1, Y2 - Y1] 10AC = [X3 - X1, Y3 - Y1] 11AD = [X4 - X1, Y4 - Y1] 12BC = [X3 - X2, Y3 - Y2] 13BD = [X4 - X2, Y4 - Y2] 14CD = [X4 - X3, Y4 - Y3] 15 16BA = [X1 - X2, Y1 - Y2] 17CA = [X1 - X3, Y1 - Y3] 18DA = [X1 - X4, Y1 - Y4] 19CB = [X2 - X3, Y2 - Y3] 20DB = [X2 - X4, Y2 - Y4] 21DC = [X3 - X4, Y3 - Y4] 22 23cp1 = cross(AB, AC) 24cp2 = cross(AB, AD) 25cp3 = cross(CD, CA) 26cp4 = cross(CD, CB) 27 28flag = True 29 30A = (X1, Y1) 31B = (X2, Y2) 32C = (X3, Y3) 33D = (X4, Y4) 34 35if A > B: 36 A, B = B, A 37if C > D: 38 C, D = D, C 39 40if cp1 == 0 and cp2 == 0 and cp3 == 0 and cp4 == 0: 41 if max(A, C) > min(B, D): 42 flag = False 43else: 44 if cp1 * cp2 > 0 or cp3 * cp4 > 0: 45 flag = False 46 47if flag: 48 print('Yes') 49else: 50 print('No')

C++の不正解コード

C++

1#include <bits/stdc++.h> 2#include <math.h> 3using namespace std; 4#define ll long long 5 6/* judge by yes or no */ 7void judge(bool x) { if (x) { cout << "Yes" << endl; } else { cout << "No" << endl; } } 8 9ll cross_product(vector<ll> x, vector<ll> y) { 10 ll ans = x.at(0) * y.at(1) - y.at(0) * x.at(1); 11 return ans; 12} 13 14pair<ll, ll> larger(pair<ll, ll> x, pair<ll, ll> y) { 15 if (x < y) { 16 return y; 17 } 18 else { 19 return x; 20 } 21} 22pair<ll, ll> smaller(pair<ll, ll> x, pair<ll, ll> y) { 23 if (x > y) { 24 return y; 25 } 26 else { 27 return x; 28 } 29} 30 31void solve() { 32 ll x1, y1, x2, y2, x3, y3, x4, y4; cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4; 33 34 pair<ll, ll> A = {x1, y1}; 35 pair<ll, ll> B = {x2, y2}; 36 pair<ll, ll> C = {x3, y3}; 37 pair<ll, ll> D = {x4, y4}; 38 39 if (A > B) { 40 swap(A, B); 41 } 42 if (C > D) { 43 swap(C, D); 44 } 45 46 x1 = A.first; y1 = A.second; 47 x2 = B.first; y2 = B.second; 48 x3 = C.first; y3 = C.second; 49 x4 = D.first; y4 = D.second; 50 51 vector<ll> AB = {x2 - x1, y2 - y1}; vector<ll> BA = {x1 - x2, y1 - y2}; 52 vector<ll> AC = {x3 - x1, y3 - y1}; vector<ll> CA = {x1 - x3, y1 - y3}; 53 vector<ll> AD = {x4 - x1, y4 - y1}; vector<ll> DA = {x1 - x4, y1 - y4}; 54 vector<ll> BC = {x3 - x2, y3 - y2}; vector<ll> CB = {x2 - x3, y2 - y3}; 55 vector<ll> BD = {x4 - x2, y4 - y2}; vector<ll> DB = {x2 - x4, y2 - y4}; 56 vector<ll> CD = {x4 - x3, y4 - y3}; vector<ll> DC = {x3 - x4, y3 - y4}; 57 58 ll cp1 = cross_product(AB, AC); 59 ll cp2 = cross_product(AB, AD); 60 ll cp3 = cross_product(CD, CA); 61 ll cp4 = cross_product(CD, CB); 62 63 bool flag = true; 64 65 if (cp1 == 0 && cp2 == 0 && cp3 == 0 && cp4 == 0) { 66 if (larger(A, C) > smaller(B, D)) { 67 flag = false; 68 } 69 } 70 else { 71 if (cp1 * cp2 > 0 || cp3 * cp4 > 0) { 72 flag = false; 73 } 74 } 75 76 judge(flag); 77} 78 79int main() { 80 solve(); 81}

質問

両者ともに方針は同じで、クロス積の正負に着目することで点と点の位置関係を見るというものです。Pythonの方ではpairの比較でmin, maxを使いましたがC++ではそれは使えないため自分で関数を作りました。まだC++の方は特に初心者である為どこがダメで不正解になってしまうのかがわかりませんでした。素人質問にて恐縮ですが、お力添えいただける箇所がございましたら、何卒ご教授のほど宜しくお願い申し上げます。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答3

0

ベストアンサー

こちらの入力例でデバッグすれば、問題点が分かると思います。

text

10 0 21000000000 1000000000 30 1000000000 41000000000 0

投稿2022/07/21 13:00

actorbug

総合スコア2212

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

kay_ventris4

2022/07/21 13:25

ご回答ありがとうございます。確かに、Yesを期待したところNoが出力されていました。 これは、10^9が1であったときには正常に動いていたことから、オーバーフローが原因という理解で正しいのでしょうか…?
actorbug

2022/07/21 13:32

デバッガで追えばわかりますが、この入力だと cp1 = cp4 = 10^18、cp2 = cp3 = -10^18 になります。 その時、cp1 * cp2 はオーバーフローして 5527149226598858752 となり、正負が変わってしまいます。
kay_ventris4

2022/07/21 14:02 編集

if ((cp1 > 0 && cp2 > 0) || (cp1 < 0 && cp2 < 0)) { flag = false; } if ((cp3 > 0 && cp4 > 0) || (cp3 < 0 && cp4 < 0)) { flag = false; } と書き換えることで正解が得られました!必ずしも気づけずとも、無闇に大きな数の掛け算をしてはいけなかったんですね。以前もお助け頂き、誠にありがとうございます。
guest

0

同じように作ったつもりであるならば、swapをそこでやってはまずいでしょう。中身変わってしまいますよ。

投稿2022/07/21 11:08

ardin

総合スコア544

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

kay_ventris4

2022/07/21 11:36

Pythonの if A > B: A, B = B, A if C > D: C, D = D, C とC++の if (A > B) { swap(A, B); } if (C > D) { swap(C, D); } が対応していないということでしょうか?
guest

0

一応私のところでC++のコードをコンパイルして
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_ah
の入力例12345をやってみました。結果は

1 1
2 2
1 2
2 1
Yes

1 2
2 2
1 1
1 3
Yes

100000001 200000000
200000000 200000000
100000000 100000000
100000000 300000000
No

1 1
3 3
2 2
4 4
Yes

4 1
3 2
2 3
1 4
No

でして、なにが悪いのか分かりませんでした。pythonとCで結果が変わると言うなら入力も書いたほうがいいのでは?と思います。

投稿2022/07/21 08:57

kokawa2003

総合スコア217

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

kay_ventris4

2022/07/21 11:38

おっしゃる通りなのですが、この問題では入力例以外のテストケースが公開されておりません。自分でも思いつく限りのケースで試してみたのですが、WAを出すテストケースが分からず、この形で質問させて頂くことと致しました。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問