Submission #70474

#	Time	Username	Problem	Language	Result	Execution time	Memory
70474		ksun48	The Forest of Fangorn (CEOI14_fangorn)	C++14	50 / 100	3046 ms	1220 KiB

fangorn

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const double EPS = 1e-8;

template <class T>
struct Point {
	typedef Point P;
	T x, y;
	explicit Point(T x=0, T y=0) : x(x), y(y) {}
	bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
	bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
	P operator+(P p) const { return P(x+p.x, y+p.y); }
	P operator-(P p) const { return P(x-p.x, y-p.y); }
	P operator*(T d) const { return P(x*d, y*d); }
	P operator/(T d) const { return P(x/d, y/d); }
	T dot(P p) const { return x*p.x + y*p.y; }
	T cross(P p) const { return x*p.y - y*p.x; }
	T cross(P a, P b) const { return (a-*this).cross(b-*this); }
	T dist2() const { return x*x + y*y; }
	double dist() const { return sqrt((double)dist2()); }
	// angle to x-axis in interval [-pi, pi]
	double angle() const { return atan2(y, x); }
	P unit() const { return *this/dist(); } // makes dist()=1
	P perp() const { return P(-y, x); } // rotates +90 degrees
	P normal() const { return perp().unit(); }
	// returns point rotated 'a' radians ccw around the origin
	P rotate(double a) const {
		return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
};

template <class P>
int lineIntersection(const P& s1, const P& e1, const P& s2,
		const P& e2, P& r) {
	if ((e1-s1).cross(e2-s2)) { //if not parallell
		r = s2-(e2-s2)*(e1-s1).cross(s2-s1)/(e1-s1).cross(e2-s2);
		return 1;
	} else
		return -((e1-s1).cross(s2-s1)==0 || s2==e2);
}

int main(){
    LL w, h;
    cin >> w >> h;
    Point<double> start_point;
    cin >> start_point.x >> start_point.y;
    int c;
    cin >> c;
    vector<Point<double> > camps(c);
    for(int i = 0; i < c; i++){
        cin >> camps[i].x >> camps[i].y;
    }
    int n;
    cin >> n;
    vector<Point<double> > trees(n);
    for(int i = 0; i < n; i++){
        cin >> trees[i].x >> trees[i].y;
    }
    vector<Point<double> > ray_start, ray_end;
    for(int i = 0; i < n; i++){
        // biggest, smallest angle();
        int idx_min = -1;
        double angle_min;
        int idx_max = -1;
        double angle_max;
        for(int j = 0; j < n; j++){
            if(i == j) continue;
            Point<double> diff_dir = trees[j] - trees[i];
            Point<double> base_dir = start_point - trees[i];
            double delta = Point<double>(1,0).rotate(diff_dir.angle() - base_dir.angle()).angle();
            if(idx_min == -1 || delta < angle_min){
                idx_min = j;
                angle_min = delta;
            }
            if(idx_max == -1 || delta > angle_max){
                idx_max = j;
                angle_max = delta;
            }
        }
        ray_start.push_back(trees[i]);
        ray_end.push_back(trees[i] * 2 - trees[idx_min]);
        ray_start.push_back(trees[i]);
        ray_end.push_back(trees[i] * 2 - trees[idx_max]);
    }
    vector<int> ans;
    for(int i = 0; i < camps.size(); i++){
        int ok = 1;
        // check to see if these are okay
        for(int a = 0; a < ray_start.size(); a++){
            for(int b = 0; b < ray_start.size(); b++){
                if(a == b) continue;
                Point<double> s1 = ray_start[a];
                Point<double> e1 = ray_end[a];
                Point<double> s2 = ray_start[b];
                Point<double> e2 = ray_end[b];
                Point<double> r;
                if(lineIntersection(s1, e1, s2, e2, r) != 1) continue;
                if((r-s1).dot(e1-s1) < -EPS || (r-s2).dot(e2-s2) < -EPS) continue;
                Point<double> sep1 = e1 - s1;
                Point<double> sep2 = e2 - s2;
                Point<double> ang1 = start_point - r;
                Point<double> ang2 = camps[i] - r;
                vector<pair<double, int> > f = 
                {{sep1.angle(), 0}, {sep2.angle(), 0}, 
                 {ang1.angle(), 1}, {ang2.angle(), 1}};
                sort(f.begin(), f.end());
                if(f[0].second == f[2].second){
                    ok = 0;
                }
            }
        }
        if(ok) ans.push_back(i);
    }
    cout << ans.size() << '\n';
    for(int x : ans){
        cout << x + 1 << ' ';
    }
    cout << endl;
}

Compilation message (stderr)

fangorn.cpp: In function 'int main()':
fangorn.cpp:87:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < camps.size(); i++){
                    ~~^~~~~~~~~~~~~~
fangorn.cpp:90:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int a = 0; a < ray_start.size(); a++){
                        ~~^~~~~~~~~~~~~~~~~~
fangorn.cpp:91:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int b = 0; b < ray_start.size(); b++){
                            ~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 20