# QuickHull use Divide and Conquer But need Help !!!

• Use QuickHull for this question, but i cant remove duplicates when one point on the edge, so i use set, but anyone can tell me how to solve this without set?

``````/**
* Definition for a point.
* struct Point {
*     int x;
*     int y;
*     Point() : x(0), y(0) {}
*     Point(int a, int b) : x(a), y(b) {}
* };
*/
class Solution {
public:
struct comp {
bool operator()(struct Point a, struct Point  b) {

if(a.x == b.x && a.y == b.y) {
return false;
} else {
if(a.x != b.x) {
return a.x < b.x;
} else {
return a.y < b.y;
}
}
}

};
vector<Point> outerTrees(vector<Point>& points) {
sort(points.begin(), points.end(), cmp);
Point a = points[0];
Point b = points[points.size() - 1];
vector<Point> upper = quickHull(points, a, b);
vector<Point> lower = quickHull(points, b, a);
upper.insert(upper.end(), lower.begin() + 1, lower.end() - 1);
set<Point, comp> set;
for (Point p : upper) set.insert(p);
vector<Point> res(set.begin(), set.end());
return res;
}

int cross(Point a, Point b, Point c) {
return (a.x - c.x) * (b.y - c.y) - (b.x - c.x) * (a.y - c.y);
}

static bool cmp(Point a, Point b) {
if (a.x == b.x && a.y == b.y) return false;
return a.x < b. x || (a.x == b.x && a.y < b.y);
}

bool inLine(Point a, Point b, Point c) {
if (cross(b, c, a) != 0) return false;
if (c.x == a.x && c.y == a.y) return false;
if (c.x == b.x && c.y == b.y) return false;
if (c.x < min(b.x, a.x) || c.x > max(a.x, b.x)) return false;
if (c.y < min(a.y, b.y) || c.y > max(a.y, b.y)) return false;
return true;
}

vector<Point> quickHull(vector<Point> points, Point a, Point b) {
vector<Point> res;
int n = points.size();
int maxx = INT_MIN;
int id = -1;

for (int i = 0; i < points.size(); i++) {
int tmp = cross(b, points[i], a);
if (tmp > 0) {
if (tmp > maxx) {
maxx = tmp;
id = i;
}
}
}

if (id == -1) {
res.push_back(a);
for (int i = 0; i < points.size(); i++) {
if(inLine(a, b, points[i])) {
res.push_back(points[i]);
}
}
res.push_back(b);
} else {
Point c = points[id];
vector<Point> lPoints;
vector<Point> rPoints;

for (int i = 0; i < points.size(); i++) {
if (cross(c, points[i], a) >= 0) lPoints.push_back(points[i]);
if (cross(b, points[i], c) >= 0) rPoints.push_back(points[i]);
}

vector<Point> left = quickHull(lPoints, a, c);
vector<Point> right = quickHull(rPoints, c, b);

res.insert(res.end(), left.begin(), left.end());
res.insert(res.end(), right.begin() + 1, right.end());
}
return res;
}

};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.