Página Principal

MC521-1s2014

MC621-2s2014

MC521-1s2015

MC621-2s2015

MC521-1s2016

Conteúdo

Área Reservada

edit sidebar

LA 6532

Solução: Lucas Castro

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <set>
#include <string>
#include <cmath>

using namespace std;

#define INI 0
#define FIM 1
#define KID 2

#define EPS 1e-15
#define PI acos(-1.0)

long double cmp(long double a, long double b){
    if(fabs(a-b) < EPS) return 0;
    if(a > b) return 1;
    return -1;
}

struct pt{
    long double x,y;
    long double ang;    
    int idseg;  
    int id;

    pt() {}
    pt(long double x, long double y) : x(x) , y(y) {}  
};

long double norma(pt a){
    return hypot(a.x,a.y);
}

pt operator -(pt a, pt b){
    return pt(a.x - b.x, a.y - b.y);
}

long double operator %(pt a, pt b){
    return a.x*b.y - a.y*b.x;
}

bool cmp_ang(pt a, pt b){
    return a.ang < b.ang;
}

struct seg{
    pt a,b;

    seg() {}
    seg(pt a, pt b) : a(a) , b(b) {}    
};



pt pivo;
pt P;
vector<pt> K;
vector<seg> segs,segsaux;
vector<pt> pts;


long double dist(int idseg){
    pt ab = segs[idseg].a - segs[idseg].b;
    return norma(P)/(fabs((P%segs[idseg].a)/(segs[idseg].a%ab)) + fabs((P%segs[idseg].b)/(segs[idseg].b%ab)));
}


struct comp {
        inline bool operator() (const int i, const int j) {
                return dist(i) < dist(j);
        }
};

int ns,nk,nw;
void gera_pts(vector<pt> &pts, int ind){
    pt p,q;
    pts.clear();
    for(int i = 0 ; i < K.size() ; i++){
        if(i == ind) continue;
        p = K[i] - pivo;
        p.ang = PI - atan2(p.y,p.x);
        p.id = KID;
        p.idseg = -1;
        pts.push_back(p);        
    }
    segs.resize(segsaux.size());
    for(int i = 0 ; i < segsaux.size() ; i++){        
        p = segsaux[i].a - pivo;
        q = segsaux[i].b - pivo;
        p.ang = PI - atan2(p.y,p.x);
        q.ang = PI - atan2(q.y,q.x);

        if(cmp(p.ang,q.ang) >= 0) swap(p,q);
        if(cmp(q.ang - p.ang,PI) >= 0) swap(p,q);

        p.id = INI;
        q.id = FIM;
        p.idseg = q.idseg = i;        

        pts.push_back(p);
        pts.push_back(q);
        segs[i] = seg(p,q);        
    }

    sort(pts.begin(),pts.end(), cmp_ang);    
}

set<int, comp> s;
set<int, comp>::iterator it;
int main(){    
    while(scanf(" %d %d %d",&ns,&nk,&nw) == 3){
        int x,y;
        pt paux;

        K.clear();        
        segs.clear();
        segsaux.clear();

        for(int i = 0 ; i < nk ; i++){
            scanf(" %Lf %Lf",&paux.x,&paux.y);
            paux.idseg = -1;          
            K.push_back(paux);
        }  

        seg saux;
        for(int i = 0 ; i < nw ; i++){
            scanf(" %Lf %Lf",&paux.x,&paux.y);            
            paux.idseg = i;
            saux.a = paux;              

            scanf(" %Lf %Lf",&paux.x,&paux.y);            
            paux.idseg = i;        
            saux.b = paux;

            segsaux.push_back(saux);            
        }

        for(int i = 0 ; i < ns ; i++){
            pivo = K[i];
            int iter = 2;
            int ans = 0;
            s.clear();
            gera_pts(pts,i);

            while(iter--){
                ans = 0;

                for(int j = 0 ; j < pts.size() ; j++){
                    P = pts[j];
                    if(P.id == KID){
                        if(s.size() == 0) ans++;
                        else{
                            it = s.begin();
                            if(cmp(norma(P),dist(*it)) <= 0) ans++;
                        }                        
                    }
                    else if(P.id == INI) s.insert(P.idseg);
                    else if(P.id == FIM) s.erase(P.idseg);                                        
                }
            }
            printf("%d\n",ans);
        }

    }
    return 0;
}