#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<math.h>
using namespace std;
struct Point {
double x,y;
};
struct Line{
Point l1;
Point l2;
// l1.x < l2.x always
double a; // l1 - l2 의 기울기
bool pi; // 90 도 이면 true
};
struct nP{
Point i;
double a;
};
double ccd(Point,Point,Point);
bool nP_compare(nP p,nP q)
{
if(p.a < q.a)
return true;
else if(p.a == q.a)
return p.i.x < q.i.x;
else
return false;
}
Point* get_convex(Point* input, int i_size, int* c_size) // i_size = input size, c_size = convex 점들 size
{
int i, j;
nP* s;
s = (nP*) malloc(sizeof(nP)*i_size);
Point dl = input[0];
int dli=0;
for(i=1; i<i_size; i++)
{
if(dl.x > input[i].x){
dl = input[i];
dli=i;}
else if(dl.x == input[i].x && dl.y > input[i].y)
{
dli=i;
dl = input[i];
}
}
s[0].i = dl;
s[0].a = -0;
j=0;
for(i=1;; i++,j++)
{
while((dl.x == input[j].x && dl.y == input[j].y)&&(j<i_size))j++;
if(j==i_size)break;
s[i].i = input[j];
s[i].a = atan2(input[j].y-dl.y,input[j].x-dl.x);
}
sort(s+1,s+i,nP_compare);
i_size = i;
Point* c = (Point*)malloc(sizeof(Point)*i_size);
c[0] = input[dli];
j=1;
for(i=1; i<i_size; i++)
{
if(j==1)
{
c[j] = s[i].i;
j++;
}
else
{
double did = ccd(c[j-2],c[j-1],s[i].i);
if(did>0){
c[j] = s[i].i;
j++;
}
else
{
j--;
i--;
}
}
}
*c_size = j;
printf("%d\n",j);
for(i=0; i<j; i++)
{
printf("%lf %lf\n",c[i].x,c[i].y);
}
return c;
}
Line Make_Line(Point x1,Point x2)
{
Line l;
if(x1.x<x2.x){
l.l1 = x1;
l.l2 = x2;
}
else if(x1.x > x2.x){
l.l1 = x2;
l.l2 = x1;
}
else
{
if(x1.y > x2.y)
{
l.l1 = x2;
l.l2 = x1;
}
else
{
l.l1 = x1;
l.l2 = x2;
}
}
if(l.l1.x == l.l2.x)
{
l.pi = true;
l.a=0;
}
else
{
l.pi=false;
l.a = (l.l2.y - l.l1.y)/(l.l2.x - l.l1.x);
}
return l;
}
double ccd(Point p1,Point p2,Point p3)
{
return (p1.x*p2.y + p2.x*p3.y + p3.x*p1.y) - (p1.y*p2.x + p2.y*p3.x + p3.y*p1.x);
}
bool is_cross(Line as1,Line as2)
{
double p1 = ccd(as1.l1,as1.l2,as2.l1);
double p2 = ccd(as1.l1,as1.l2,as2.l2);
double p3 = ccd(as1.l1,as2.l1,as2.l2);
double p4 = ccd(as1.l2,as2.l1,as2.l2);
if(p1*p2<=0 && p3*p4<=0)return true;
return false;
}
Point get_cross_point(Line as1, Line as2)
{
Point t;
t.x=-1;
t.y=-1;
if(is_cross(as1,as2))
{
if(as2.pi)
{
if(as1.pi)
{
if(as1.l1.x == as2.l2.x)
{
if(as1.l1.y == as2.l2.y)
{
t.x = as1.l1.x;
t.y = as1.l1.y;
}
else if(as2.l1.y == as1.l2.y)
{
t.x = as2.l1.x;
t.y = as2.l1.y;
}
else
{
if(as1.l1.y > as2.l2.y || as1.l2.y < as2.l1.y)
{
t.x = -1;
t.y = -1;
}
else
{
t.x = -2; // 선분이 일치함 처리
t.y = -2;
}
}
}
else
{
t.x = -1;
t.y = -1;
}
}
else
{
t.x = as2.l1.x;
t.y = as1.l1.y + as1.a*(t.x - as1.l1.x);
}
}
else
{
if(as1.pi)
{
t.x = as1.l1.x;
t.y = as2.l1.y + as2.a*(t.x - as2.l1.x);
}
else
{
if(as1.a == as2.a)
{
if(as1.l1.x == as2.l2.x && as1.l1.y == as2.l2.y)
{
t.x = as1.l1.x;
t.y = as1.l1.y;
}
else if(as2.l1.x == as1.l2.x && as2.l1.y == as1.l2.y)
{
t.x = as2.l1.x;
t.y = as2.l1.y;
}
else
{
if(as1.l1.y > as2.l1.y || as1.l2.y < as2.l1.y)
{
t.x = -1;
t.y = -1;
}
else
{
t.x = -2; // 선분이 일치하는 경우
t.y = -2;
}
}
}
else
{
double temp = (as2.a*(as1.l1.x - as2.l1.x) - (as1.l1.y - as2.l1.y))/(as1.a - as2.a);
t.x = as1.l1.x + temp;
t.y = as1.l1.y + as1.a*temp;
}
}
}
}
return t;
}
void input2()
{
int n;
double r;
scanf("%d %lf",&n,&r);
Point* ip = (Point*)malloc(sizeof(Point)*n);
for(int i=0; i<n; i++)
{
scanf("%lf %lf",&ip[i].x,&ip[i].y);
}
Point* jp = get_convex(ip,n,&n);
double pi = acos(0.0)*2;
double res = r*2*pi;
for(int i=0;i<n;i++)
{
int j = (i+1)%n;
double xx = jp[i].x - jp[j].x;
double yy = jp[i].y - jp[j].y;
res += sqrt(xx*xx+yy*yy);
}
printf("%.9lf\n",res);
}
int main()
{
int t;
{
//input();
input2();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
1316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
