Submission #9142

#TimeUsernameProblemLanguageResultExecution timeMemory
9142effservWall construction (kriii2_WA)C++98
4 / 4
96 ms5712 KiB
#include <cstdio> #include <cmath> #include <vector> #include <algorithm> #include <map> using namespace std; #define maxS 1001 typedef pair <int, int> point; typedef struct _node { int i; int a; int b; int c; int d; bool det; }node; node nn[maxS]; int x[maxS], y[maxS]; vector <int> one[maxS], two[maxS], three[maxS], four[maxS]; int cmp1(node i, node j) { if (i.det == true && j.det == true) { return i.i < j.i; } return i.det > j.det; } int IsCandidate(point bp, point cp, point ap) { point p1(cp.first - bp.first, cp.second - bp.second); point p2(ap.first - bp.first, ap.second - bp.second); return p2.second*p1.first - p1.second*p2.first; } double dist(point ap1, point ap2) { return hypot(ap2.first - ap1.first, ap2.second - ap1.second); } vector <point> points; int main() { // freopen("input.txt", "r", stdin); int n,r; scanf("%d%d", &n, &r); for (int i = 0; i < n; i++) { scanf("%d%d", &x[i], &y[i]); nn[i].det = true; } for (int i = 0; i < n; i++) { nn[i].i = i; int a = 0; int b = 0; int c = 0; int d = 0; for (int j = 0; j < n; j++) { if (i == j || nn[j].det == false) continue; if (x[j] - x[i] >= 0 && y[j] - y[i] >= 0) { a++; one[nn[i].i].push_back(j); } if (x[j] - x[i] <= 0 && y[j] - y[i] >= 0) { b++; two[nn[i].i].push_back(j); } if (x[j] - x[i] <= 0 && y[j] - y[i] <= 0) { c++; three[nn[i].i].push_back(j); } if (x[j] - x[i] >= 0 && y[j] - y[i] <= 0) { d++; four[nn[i].i].push_back(j); } if (a && b && c && d) { nn[i].det = false; break; } } nn[i].a = a; nn[i].b = b; nn[i].c = c; nn[i].d = d; } sort(nn, nn + n, cmp1); for (int i = 0; i < n; i++) { // printf("x : %d y : %d\n", x[nn[i].i], y[nn[i].i]); // printf("1사 : %d 2사 : %d 3사 : %d 4사 : %d\n", nn[i].a, nn[i].b, nn[i].c, nn[i].d); if (nn[i].det == false) { n = i; // printf("새로 바뀐 n 은 : %d\n", n); break; } } for (int i = 0; i < n; i++) { bool onedet = nn[i].a ? false : true; bool twodet = nn[i].b ? false : true; bool thrdet = nn[i].c ? false : true; bool fourdet = nn[i].d ? false : true; if (onedet == true && twodet == true) continue; if (onedet == true && fourdet == true) continue; if (twodet == true && thrdet == true) continue; if (thrdet == true && fourdet == true) continue; if (onedet == false && thrdet == false) { int onesz = one[nn[i].i].size(); int thrsz = three[nn[i].i].size(); bool twodet2 = false; bool fourdet2 = false; bool otherdet = false; for (int j = 0; j < onesz; j++) { int tmp = one[nn[i].i][j]; for (int k = 0; k < thrsz; k++) { int dx = x[tmp] + x[three[nn[i].i][k]] - 2 * x[nn[i].i]; int dy = y[tmp] + y[three[nn[i].i][k]] - 2 * y[nn[i].i]; if (dx <= 0 && dy >= 0) twodet2 = true; else if (dx >= 0 && dy <= 0) fourdet2 = true; else otherdet = true; } if (twodet2 == true && fourdet2 == true) { nn[i].det = false; break; } } if (twodet2 == false && fourdet2 == false) { if (otherdet == true) { nn[i].det = false; } else { printf("오류\n"); return 0; } } } if (twodet == false && fourdet == false) { int twosz = two[nn[i].i].size(); int foursz = four[nn[i].i].size(); bool onedet2 = false; bool thrdet2 = false; bool otherdet = false; for (int j = 0; j < twosz; j++) { int tmp = two[nn[i].i][j]; for (int k = 0; k < foursz; k++) { int dx = x[tmp] + x[four[nn[i].i][k]] - 2 * x[nn[i].i]; int dy = y[tmp] + y[four[nn[i].i][k]] - 2 * y[nn[i].i]; if (dx >= 0 && dy >= 0) onedet2 = true; else if (dx <= 0 && dy <= 0) thrdet2 = true; else otherdet = true; } if (onedet2 == true && thrdet2 == true) { nn[i].det = false; break; } } if (onedet2 == false && thrdet2 == false) { if (otherdet == true) { nn[i].det = false; } else { printf("오류\n"); return 0; } } } } sort(nn, nn + n, cmp1); for (int i = 0; i < n; i++) { // printf("x : %d y : %d\n", x[nn[i].i], y[nn[i].i]); // printf("1사 : %d 2사 : %d 3사 : %d 4사 : %d\n", nn[i].a, nn[i].b, nn[i].c, nn[i].d); if (nn[i].det == false) { n = i; // printf("새로 바뀐 n 은 : %d\n", n); break; } } int minXi = -1, minX = 10000000; for (int i = 0; i < n; i++) { points.push_back(point(x[nn[i].i], y[nn[i].i])); if (minX > x[nn[i].i]) { minX = x[nn[i].i]; minXi = i; } } vector <point> boundary; boundary.push_back(point(points[minXi].first, points[minXi].second)); double res = 0; while (1) { point bp = boundary.back(); point cp = points[0]; for (int i = 0; i < n; i++) { // if (bp == points[i]) // continue; // printf("%d point x : %d y : %d\n",i,points[i].first, points[i].second); // printf("%d cp x : %d y : %d\n", i, cp.first, cp.second); int det = IsCandidate(bp, cp, points[i]); // printf("%d\n", det); if (det < 0 || (det == 0 && (dist(points[i], bp) > dist(cp,bp)) )) { // printf("%d %d\n", points[i].first, points[i].second); cp = points[i]; } } res += dist(cp, bp); if (cp == boundary[0]) break; boundary.push_back(cp); } printf("%lf\n", res + (2 * acos(0.0)*2 *r)); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...