开心啦! THUOJ不过不知道是什么鬼畜精度问题,不管了^v^
板子好用^v^
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 | #include<iostream> #include<iomanip> #include<string> #include<algorithm> #include<vector> #include<cmath> using namespace std; struct point { double x, y; long long id; point() :x(0), y(0) {} bool operator ==(const point& p) const { return x == p.x && y == p.y; } }PP; //PP: Polar Point vector<point> points; double area2(point p, point q, point s) { /* |p.x p.y 1| |q.x q.y 1| == 2*DirectedTriangleArea(p,q,s) |s.x s.y 1| */ return p.x * q.y - s.x * q.y + q.x * s.y - q.x * p.y + s.x * p.y - p.x * s.y; } bool toLeftTest(point p, point q, point s) { //When return value large than 0, S is on the left side of ray PQ return area2(p, q, s) > 0; } bool toLeftTest2(point p, point q, point s) { //When return value large than 0, S is on the left side of ray PQ return area2(p, q, s) >= 0; } bool cmp(const point& p1, const point& p2) { // Sort according to polar angle return PP == p1 || !(PP == p2) && toLeftTest(PP, p1, p2); } point LTL(vector<point>& points) { //Lowest then leftmost point ltl = points[0]; for (int i = 1; i < points.size(); i++) { if (points[i].y < ltl.y || points[i].y == ltl.y && points[i].x < ltl.x) ltl = points[i]; } return ltl; } vector<point> grahamScan() { PP = LTL(points); sort(points.begin(), points.end(), cmp); vector<point> S, T; S.push_back(points[0]); S.push_back(points[1]); for (int i = points.size() - 1; i > 1; i--)T.push_back(points[i]); while (!T.empty()) { if (toLeftTest2(S[S.size() - 2], S[S.size() - 1], T[T.size() - 1])) { S.push_back(T[T.size() - 1]); T.pop_back(); } else S.pop_back(); } return S; } double dist(point x, point y) { return sqrt((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y)); } int main() { ios::sync_with_stdio(false); long long n; cin >> n; for (int i = 1; i <= n; i++) { point tmp; cin >> tmp.x >> tmp.y; tmp.id = i; points.push_back(tmp); } vector<point> result; if (points.size() > 2)result = grahamScan(); else result = points; double res = 0; for (int i = 0; i < result.size(); i++) { res += dist(result[i % result.size()], result[(i + 1) % result.size()]); } cout.setf(ios::fixed); cout << setprecision(2) << res; } |