글 읽기 - 어느 케이스에서 틀리는 것인지 잘모르겠습니다

20151571 8년 전 0

어느 부분에서 틀린 것 일까요??

다른 예제를 넣어봐도 정상적으로 나오는 것 같은데....

일직선인 경우까지도 다 넣어봤는데 도저히 뭐가 틀렸는지 모르겠네요...

도와주세요 ㅜㅜ

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair < int , int > ll;
typedef pair < double, int > di;

int ccw(ll a, ll b, ll c){
        long long num = a.first*b.second+b.first*c.second+c.first*a.second
                -a.second*b.first-b.second*c.first-c.second*a.first;
        if(num>0)
                return 1;
        else if(num<0)
                return -1;
        return 0;
}

double gradient(ll a, ll b){
        return (double)(b.second-a.second)/(b.first-a.first);
}

int dist(ll a , ll b){
        return (a.first - b.first)*(a.first-b.first)
                +(a.second-b.second)*(a.second-b.second);
}

int main(){
        int n,ccwnum=0,zz=0,zzz=0;
        vector < ll > v;
        vector < pair < di , ll > > g;
        vector < ll > ans;
        scanf("%d",&n);
        v.clear(),g.clear(),ans.clear();
        for(int i=0;i<n;i++){
                int a,b;
                scanf("%d%d",&a,&b);
                v.push_back(make_pair(a,b));
        }
        sort(v.begin(),v.end());
        g.push_back(make_pair(make_pair(-989674,0.0),v[0]));
        for(int i=1;i<(int)v.size();++i){
                double d;
                if(v[0].second == v[i].second)//y좌표 같은 경우 체크
                        zzz++;
                if(v[0].first != v[i].first)//둘다 안 같은 경우
                        d = gradient(v[0],v[i]);

                else if(v[0].first == v[i].first){//x좌표 같은 경우
                        d = 989676867-v[i].second+v[i].first;//나올 수 없는 값 대입
                        zz++;//개수 체크
                }
                g.push_back(make_pair(
                                        make_pair(d,dist(v[0],v[i]))
                                        ,v[i]));//기울기, 거리, 좌표 저장
        }
        sort(g.begin(),g.end());//기울기 , 거리 순으로 정렬
        for(int i=0;i<2;i++)
                ans.push_back(g[i].second);//첫번재(기준), 두번째 좌표 저장
        int num=2,size=1;//현재 index 상으로 2번째 점, 마지막 점은 ans 벡터에 1에 저장되어 있음.
        while(num<=n){//다시 돌아 오는 경우 있어서 n까지 한다.
                ccwnum = ccw(ans[size-1],ans[size],g[num%n].second);
                if(ccwnum<=0)
                        ans.pop_back();
                else
                        size++;
                if(g[num%n].second !=v[0])//대신에 기준인 좌표는 넣지 않느다.
                        ans.push_back(g[num%n].second);
                num++;
        }
        if(zz==n-1)//기준과 x 좌표가 모두 같아 일직선인 경우
                ans.push_back(g[1].second);
        if(zzz==n-1)//기준과 y좌표가 모두 같아 일직선인 경우
                ans.push_back(g[n-1].second);

        printf("%d\n",(int)ans.size());//ans 벡터의 사이즈 출력
        return 0;
}

20151571 8년 전 0

위 경우를 제대로 처리 하려고 while 문으로 바꿔서 해보았는데

여전히 틀렸습니다가 뜨네요.....

다른 테스트 케이스도 제대로 되는데

이런 방식으로 하면 안되는 것인가요....?

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair < int , int > ll;
typedef pair < double, int > di;

int ccw(ll a, ll b, ll c){
        long long num = a.first*b.second+b.first*c.second+c.first*a.second
                -a.second*b.first-b.second*c.first-c.second*a.first;
        if(num>0)
                return 1;
        else if(num<0)
                return -1;
        return 0;
}

double gradient(ll a, ll b){
        return (double)(b.second-a.second)/(b.first-a.first);
}

int dist(ll a , ll b){
        return (a.first - b.first)*(a.first-b.first)
                +(a.second-b.second)*(a.second-b.second);
}

int main(){
        int n,ccwnum=0,zz=0,zzz=0;
        vector < ll > v;
        vector < pair < di , ll > > g;
        vector < ll > ans;
        scanf("%d",&n);
        v.clear(),g.clear(),ans.clear();
        for(int i=0;i<n;i++){
                int a,b;
                scanf("%d%d",&a,&b);
                v.push_back(make_pair(a,b));
        }
        sort(v.begin(),v.end());
        g.push_back(make_pair(make_pair(-989674,0.0),v[0]));
        for(int i=1;i<(int)v.size();++i){
                double d;
                if(v[0].second == v[i].second)
                        zzz++;
                if(v[0].first != v[i].first)
                        d = gradient(v[0],v[i]);
                else if(v[0].first == v[i].first){
                        d = 989676867-v[i].second+v[i].first;
                        zz++;
                }
                g.push_back(make_pair(
                                        make_pair(d,dist(v[0],v[i]))
                                        ,v[i]));
        }
        sort(g.begin(),g.end());
        for(int i=0;i<2;i++)
                ans.push_back(g[i].second);
        int num=2,size=1;
        while(num<n){
                while(ccw(ans[size-1],ans[size],g[num].second)!=1 && size>=1){
                        size--;
                        ans.pop_back();
                }
                size++;
                ans.push_back(g[num].second);
                num++;
        }
        if(size>=2)
                if(ccw(ans[size-1],ans[size],ans[0])!=1)
                        ans.pop_back();
        printf("%d\n",(int)ans.size());
        return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어느 케이스에서 틀리는 것인지 잘모르겠습니다

20151571 8년 전 0

20151571 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말