#include <cstdio> #include <vector> #include <algorithm> using namespace std; struct P { P (long long x, long long y) : x(x), y(y) { } bool operator < (const P & other) const { return x != other.x ? x < other.x : y < other.y; } P operator - (const P & other) const { return P(x - other.x, y - other.y); } long long operator ^ (const P & other) const { return x * other.y - y * other.x; } long long x, y; }; int orient(P & p1, P & p2, P & p3) { long long area = (p2 - p1) ^ (p3 - p1); return area == 0 ? 0 : area > 0 ? 1 : -1; } int main() { int T; scanf("%d", &T); while (T--) { int N; scanf("%d", &N); vector<P> points; while (N--) { long long x, y; char temp[99]; scanf("%lld%lld%s", &x, &y, temp); points.push_back(P(x, y)); } sort(points.begin(), points.end()); vector<P> ch[2]; ch[0].push_back(points[0]); ch[0].push_back(points[1]); for (int i = 2; i < points.size(); i++) { ch[0].push_back(points[i]); while (ch[0].size() >= 3 && orient(points[i], ch[0][ch[0].size() - 2], ch[0][ch[0].size() - 3]) > 0) { ch[0].pop_back(); ch[0].pop_back(); ch[0].push_back(points[i]); } } ch[1].push_back(points[points.size() - 1]); ch[1].push_back(points[points.size() - 2]); for (int i = points.size() - 3; i >= 0; i--) { ch[1].push_back(points[i]); while (ch[1].size() >= 3 && orient(points[i], ch[1][ch[1].size() - 2], ch[1][ch[1].size() - 3]) > 0) { ch[1].pop_back(); ch[1].pop_back(); ch[1].push_back(points[i]); } } vector<P> ans; for (int i = 0; i < ch[0].size(); i++) { ans.push_back(ch[0][i]); } for (int i = 1; i < ch[1].size() - 1; i++) { ans.push_back(ch[1][i]); } printf("%d\n", ans.size()); for (int i = 0; i < ans.size(); i++) { printf("%lld %lld\n", ans[i].x, ans[i].y); } } return 0; }
Hello, I am a CS student from Taiwan.
I am learing English and Programming.
I'll save source code of some problems or small programs without comments in this blog.
I would recommend you not to read solution from others before you solved the problem.
(這邊專門存放沒有任何註解的小程式/OJ題目程式碼)
2014年1月31日
UVa 11626 - Convex Hull
訂閱:
張貼留言 (Atom)
沒有留言:
張貼留言