AtCoder Beginner Contest 016

[TakefumiYamamura]

http://abc016.contest.atcoder.jp/

[TakefumiYamamura]

C - 友達の友達

時間制限 : 2sec / メモリ制限 : 256MB

問題文

高橋くんはSNSの管理者をしています。このSNSではユーザ同士が友達という関係で繋がることができます。高橋くんはそれぞれのユーザの「友達の友達」が何人いるかを調べることにしました。友達関係が与えられるので、各ユーザの「友達の友達」の人数を求めてください。ただし、自分自身や友達は、「友達の友達」に含みません。

Note

幅優先するだけぽよ

#include <iostream>
#include <queue>
#define ll long long 
using namespace std;

const ll MAX = 1e9+7;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

struct Node
{
    int val;
    int depth;
};

int bfs(int start, int (*G)[10], int size){
    queue<Node> que;
    Node n = {start, 0};
    int check[10];
    Fill(check, 1);
    check[start] = 0;
    int count = 0;
    que.push(n);
    while(!que.empty()){
        Node cur = que.front();
        que.pop();
        for (int i = 0; i < size; ++i)
        {
            if(G[cur.val][i] && check[i]){
                check[i] = 0;
                Node tmp = {i, cur.depth + 1};
                if(tmp.depth == 2) count++;
                que.push(tmp);
            }
        }
    }
    return count;
}

int main(){
    int n, m;
    int G[10][10];
    Fill(G, 0);
    cin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        G[a][b] = 1;
        G[b][a] = 1;
    }

    for (int i = 0; i < n; ++i)
    {
        cout << bfs(i, G, n) << endl;
    }

}

[TakefumiYamamura]

問題

[http://abc016.contest.atcoder.jp/tasks/abc016_4:embed:cite]

メモ

苦手意識のある幾何の問題。外積の公式を使うと,あるベクトルに対して、任意の頂点が左側にあるか、右側にあるかをチェックすることができる。 そのため、線分の直行判定は、１つの線分からみたときに、もう一方の線分の2頂点が反対側にあるかどうかを、両方の線分でチェックすれば良い。（両方の線分でチェックしないといけないことに初め気づかなかった）

#include <iostream>
#include <vector>
using namespace std;

struct Point{
    double x, y;
};

class CutInTwo
{
public:
    int n;
    Point s, e;
    vector<Point> points;

    CutInTwo();
    ~CutInTwo();
    bool isRightSide(const Point a, const Point b, const Point o);
    void exec();

};

CutInTwo::CutInTwo(){
    cin >> s.x >> s.y;
    cin >> e.x >> e.y;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        double tmp_x, tmp_y;
        cin >> tmp_x >> tmp_y;
        Point p = {tmp_x, tmp_y};
        points.push_back(p);
    }
}

CutInTwo::~CutInTwo(){}

bool CutInTwo::isRightSide(const Point a, const Point b, const Point o){
    return ((a.x - o.x) * (b.y - o.y) - (a.y - o.y)* (b.x - o.x)) > 0;
}

void CutInTwo::exec(){
    points.push_back(points[0]);
    int count = 0;
    for (int i = 0; i < n; ++i)
    {
        if(isRightSide(points[i], e, s) != isRightSide(points[i+1], e, s) && isRightSide(e, points[i], points[i+1]) != isRightSide(s, points[i], points[i+1]) ){
            count++;
        }
    }
    cout << count / 2 + 1 << endl;
}

int main(){
    CutInTwo cit = CutInTwo();
    cit.exec();
}