Submission #9125

#	Time	Username	Problem	Language	Result	Execution time	Memory
9125		pichulia	Wall construction (kriii2_WA)	C++98	4 / 4	0 ms	1316 KiB

WA

#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;
    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;
}

• Subtask 1: 1 / 1
• Subtask 2: 3 / 3