oj.uz

답안 #8397

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
8397 2014-09-13T16:43:54 Z tncks0121 Wall construction (kriii2_WA) C++
1 / 4
 0 ms 1456 KB 
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h> 
#include <time.h>

using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
 
int N, R;

struct point {
	lf x, y, a;
	point (lf x = 0, lf y = 0): x(x), y(y) { } 
	bool operator < (const point &p) const { return a < p.a; }
};

point D[1005];

lf ccw (point a, point b, point c) {
	return a.x * b.y + b.x * c.y + c.x * a.y
		-  b.x * a.y - c.x * b.y - a.x * c.y;
}

vector<point> S;

int main() {
	scanf("%d%d", &N, &R);
	for(int i = 0; i < N; i++) {
		scanf("%lf%lf", &D[i].x, &D[i].y);
		if(i > 0 && (D[i].x < D[0].x || (D[i].x == D[0].x && D[i].y < D[0].y))) swap(D[0], D[i]);
	}

	for(int i = 1; i < N; i++) D[i].a = atan2(D[i].y - D[0].y, D[i].x - D[0].x);
	sort(D, D+N);

	S.push_back(D[0]);
	S.push_back(D[1]);
	for(int i = 2; i < N; i++) {
		while(S.size() >= 2 && ccw(S[S.size()-2], S[S.size()-1], D[i]) <= 0) S.pop_back();
		S.push_back(D[i]);
	}

	lf res = acos(-1) * 2 * R;
	for(int i = 0; i < S.size(); i++) {
		res += hypot(S[i].x - S[(i+1)%S.size()].x, S[i].y - S[(i+1)%S.size()].y);
	}

	printf("%.10f", res);

	return 0;
}

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1456 KB Output is correct
2 Correct 0 ms 1456 KB Output is correct
3 Correct 0 ms 1456 KB Output is correct
4 Correct 0 ms 1456 KB Output is correct
5 Correct 0 ms 1456 KB Output is correct

Subtask #2
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 1456 KB Output isn't correct
2 Halted 0 ms 0 KB -