Proficient.
Put your skills to the test.

Problem summary

Buildings stand at increasing positions on a line. A rooftop’s sunlit hours equal 12 times its visible sky angle divided by 180 degrees. Count rooftops whose hours, rounded to two decimals, are at least 6.

Source clarification. The printed numerical bound says coordinates are at least 1, but the input prose says nonnegative and the official sample uses position 0. The solution supports both interpretations.

Constraints

1 < N < 10^6; positions and heights at most 2000000; input prose permits zero and the sample uses position 0.

Worked example

An independently prepared example for this explanation.

5
0 8
4 6
6 4
7 1
11 20

3

Solution analysis

1. From a rooftop, the strongest obstruction on each side is the other rooftop with the largest positive elevation angle. Its visible sky angle is π minus those left and right obstruction angles. Lower rooftops do not block sky above the horizontal.
2. Sweep left to right, maintaining the upper convex hull of earlier rooftop points. Before inserting the current point, pop the last hull point while the last turn with the current point is nonclockwise. The remaining last point is the tangent maximizing obstruction slope. Repeat right to left using reflected x-coordinates for the right obstruction.
3. The sample sunlight amounts are 8.83,6.00,4.16,2.02,12.00 hours, so three qualify. Compute angles with atan2 and round the resulting hours to two decimal places before comparing with 6; a value just below six may still qualify.

Why it works

An interior point below a hull chord cannot yield a larger obstruction slope than both chord endpoints, so upper-hull deletion preserves the maximizing tangent. The clockwise-turn invariant ensures the surviving final vertex is the tangent from the incoming point. The two passes therefore find the exact strongest obstruction on each side; subtracting those two angles from π gives precisely the unblocked sky, and the stated rounding decides the count.

Watch out. Do not test six hours before decimal rounding. Ignore negative elevation angles. Use 64-bit cross products and long-double angle arithmetic.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
// Algorithm: From a rooftop, the strongest obstruction on each side is the other rooftop with
// the largest positive elevation angle.
using namespace std;
struct Point{
    long long x,y;
};
long long cross(Point a,Point b,Point c){
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<Point>points(n);
    for(auto&point:points){
        cin>>point.x>>point.y;
    }
    vector<long double>obstruction(n,0);
    vector<Point>hull;
    for(int pass=0;pass<2;++pass){
        hull.clear();
        for(int step=0;step<n;++step){
            int i=pass==0?step:n-1-step;
            Point current=points[i];
            if(pass==1){
                current.x=-current.x;
            }
            while(hull.size()>=2&&cross(hull[hull.size()-2],hull.back(),current)>=0){
                hull.pop_back();
            }
            if(!hull.empty()){
                long long rise=max(0LL,hull.back().y-current.y);
                obstruction[i]+=atan2(
                    static_cast<long double>(rise),static_cast<long double>(current.x-hull.back().x));
            }
            hull.push_back(current);
        }
    }
    const long double pi=acos(-1.0L);
    int answer=0;
    for(long double angle:obstruction){
        long double hours=12*(pi-angle)/pi;
        if(floor(hours*100+0.5L+1e-12L)>=600){
            ++answer;
        }
    }
    cout<<answer<<'\n';
}