凸包プログラムのメモリ超過を解消したい

このプログラムのメモリの超過を解消したい

AOJ 凸包を解いています。
c++でジャービスアルゴリズムで書きました。

発生している問題

ジャッジの際、【Memory Limit Exceeded】と言われます。答え自体は合っていると思います。
この問題を解消する方法をお教えいただけると幸いです。

ソースコード

c++
1#include <bits/stdc++.h>
2
3using namespace std;
4
5struct Point{
6    int x, y;
7};
8
9double get_vector_length( Point v ) {
10    return pow( ( v.x * v.x ) + ( v.y * v.y ), 0.5 );
11}
12
13int orientation(Point a, Point b, Point c){
14    int val = (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
15
16    if (val == 0) return 0;
17    else if (val > 0) return 1;
18    else return 2;
19}
20
21
22void convexHull(vector<Point> points, int n) {
23    if (n < 3 || n > 100000) return;
24
25    vector<Point> list;
26
27
28    int p0 = 0;
29    for (int i = 1; i < n; i++)
30        if (points[i].y < points[p0].y)
31            p0 = i;
32        else if (points[i].y == points[p0].y && points[i].x < points[p0].x)
33            p0 = i;
34
35    int A = p0, B;
36    do {
37
38        list.push_back(points[A]);
39
40        B = (A + 1) % n;
41        for (int i = 0; i < n; i++) {
42
43            if(points[i].x == points[A].x && points[i].y == points[A].y)continue;
44            if(points[i].x == points[B].x && points[i].y == points[B].y)continue;
45
46            if (orientation(points[A], points[i], points[B]) == 2)
47                B = i;
48            else if(orientation(points[A], points[i], points[B]) == 0){
49                Point AB = {points[A].x - points[B].x , points[A].y - points[B].y},
50                      Ai = {points[A].x - points[i].x , points[A].y - points[i].y};
51                double dis_AB = get_vector_length(AB);
52                double dis_Ai = get_vector_length(Ai);
53
54                if(dis_Ai < dis_AB) B = i;
55            }
56        }
57
58        A = B;
59
60    } while (A != p0);
61
62    cout << list.size() << endl;
63    for (int i = 0; i < list.size(); i++)
64        cout << list[i].x << " " << list[i].y << endl;
65}
66
67
68int main(){
69
70    int n;
71    cin >> n;
72    vector<Point> P;
73
74    for(int i = 0; i < n; i++){
75        int x, y;
76        cin >> x >> y;
77        if(x < -10000 || x > 10000 || y < -10000 || y > 10000)exit(1);
78        P.push_back({x,y});
79    }
80    convexHull(P, n);
81    return 0;
82}

補足情報（FW/ツールのバージョンなど）

yohhoy

2021/04/14 07:01

「メモリ制限 : 131072 KB」と sizeof(Point)=8 × 入力数n=100000 から考えると、(131072 * 1024) / 8 / 100000 ≒ 167.7 倍を超えて動作に必要なメモリ量が膨れているようです？これは話を極端に単純化していますが、アルゴリズムを疑うには十分ではないでしょうか。

退会済みユーザー

2021/04/14 07:03

なるほどです。どこが問題なのかすらわからなかったのでありがたいです！

行動規範の内容に同意します

回答2件

ベストアンサー

例を考えてみました．
赤●が点であり，点0,1,2が一直線上にあります．

最初，A=点0であり，次の点Bとして点1 が図の上側のように選ばれたとします．
（話的に本来どっち周りなのかまで把握してませんが，この方向に進むのだとして）

そして，

A = B;

によって，Aが図の下側の位置(点1)に移ります．
この状態で，初期のBは点2であり，次の点としてこの点2がそのまま選ばれて欲しいところでしょうが，
点0をチェックした際に，

点0,1,2は一直線上であり，
点1から見て，点2よりも点0が近い

ことから，点0が選ばれてしまいます．
…といった不具合が生じてはいないでしょうか？

投稿2021/04/14 09:01

編集2021/04/14 09:04

fana

総合スコア11949

fana

2021/04/14 09:02

うおー，図が見難い！緑の太線が，「上側」と「下側」を分けているつもりです．

fana

2021/04/14 09:09

要は，listに突っ込まれた点は以降見ないようにすべきなんじゃないか？　という．それをしてないから堂々巡りになるパターンがあって，listが膨れ上がるのだろう，という推測．間違っている場合にはその旨を明記して低評価入れといてください．

退会済みユーザー

2021/04/14 09:24

理解しました！不具合だと思いますが現在なぜか上手く言っている次第です。

行動規範の内容に同意します

C++
1            if (orientation(points[A], points[i], points[B]) == 2)
2                B = i;
3            else if(orientation(points[A], points[i], points[B]) == 0){
4                Point AB = {points[A].x - points[B].x , points[A].y - points[B].y},
5                      Ai = {points[A].x - points[i].x , points[A].y - points[i].y};
6                double dis_AB = get_vector_length(AB);
7                double dis_Ai = get_vector_length(Ai);
8
9                if(dis_Ai < dis_AB) B = i;
10            }