(※도전 완료) [도전 11일차] 백준 6990 달팽이

풀었습니다.

howtoliveworldnice.tistory.com/129

[도전 28일차] 기하 구현 끝판왕, 달팽이

※복습 : 

 

 

문제 : BOJ 6990 달팽이

 

문제 링크

 

사용 알고리즘 : 기하

 

풀이: IOI Korea 류호석님 

지금 실력으로는 구현이 불가.

직전까지 짠 코드만을 첨부함.

다음 문제로 넘어가는 것이 현명.

코드

//pentagon@sasa.hs.kr 
#include<bits/stdc++.h>
#define ll long long
#define vsort(v) sort(v.begin(),v.end());
const int INF = 1e9;
using namespace std;
int n,L;
struct S{
    int x,y,x2,y2;
    S(int a,int b,int c,int d){
        x=a; y=b; x2=c; y2=d;
    }
};
//달팽이 정보, 사건 정보 모두 S로 저장한다. 
//구간 내에서 나올 수 있는 거리의 제곱이 (10000^2)*2이므로 int형 변수로 처리 가능하다. 
vector<S> Line;
vector<S> Case;
inline bool safe(double a,double b){
    return a>=0&&a<=(double)n&&b>=0&&b<=(double)n;
}
pair<double,double> comn(S &A,S &B){
    double t;
    double s;
    double under = (B.y2-B.y)*(A.x2-A.x)-(B.x2-B.x)*(A.y2-A.y);
    pair<double,double> fail = make_pair(-1.0,-1.0);
    if(under==0.0)
        return fail;
    double _t = (B.x2-B.x)*(A.y-B.y) - (B.y2-B.y)*(A.x-B.x);
    double _s = (A.x2-A.x)*(A.y-B.y) - (A.y2-A.y)*(A.x-B.x); 
    t=_t/under;
    s=_s/under;
    if(t<0.0 || t>1.0 ||s<0.0 || s>1.0) 
        return fail;
    if(_t==0.0 && _s==0.0)
        return make_pair(-2.0,-2.0);
    return make_pair(A.x+t*(A.x2-A.x),B.y+t*(B.y2-B.y));
}
void meet(int a,int b){
    S&A=Line[a],&B=Line[b];
    double a1=A.x,a2=A.y,b1=B.x,b2=B.y;
    double c1,c2;
    tie(c1,c2)=comn(A,B);
    if(c1==-1.0 && c2==-1.0)
        return;
    if(c1==-2.0 && c2 ==-2.0){
        if((A.x2-A.x) * (B.x2-B.x)>=0 && (A.y2-A.y) * (B.y2-B.y)>=0)
            
    }
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>L;
    int t=1e4;
    for(int i=0,a,b,c,d;i<n;i++){
        cin>>a>>b>>c>>d;
        c-=a; d-=b;
        Line.push_back(S(a,b,a+c*t,b+d*t));
    }
    Line.push_back(S(0,0,L,0)); Line.push_back(S(0,0,0,L));
    Line.push_back(S(L,0,L,L)); Line.push_back(S(0,L,L,L));
    //충돌 처리  
    for(int i=0;i<n+3;i++)
        for(int j=i+1;j<n+4;j++)
            Meet(i,j);
             
}

 

기하