Proficient.
Put your skills to the test.

Problem summary

Metal nails are represented by closed line segments. The last input segment is a live wire. A nail is unsafe if it touches the wire directly or through a chain of touching nails. Count the safe nails.

Constraints

At most 1000 nails; integer coordinates between 0 and 10000. Endpoint contact and overlapping segments count as touching.

Worked example

An independently prepared example for this explanation.

5 2 8 2
3 4 3 1
7 1 6 4
3 3 0 3
6 3 1 1

2

Solution analysis

1. Treat each segment, including the wire, as a vertex of a connection graph. Two vertices are adjacent exactly when their geometric segments intersect, including endpoint touches or collinear overlaps.
2. Test all segment pairs. First reject disjoint x or y bounding intervals. Then use cross products: intersecting segments must straddle each other’s supporting lines, allowing zero orientation for contact. Bounding boxes handle the collinear case.
3. Union every touching pair in a disjoint-set structure. Connectivity is transitive, which models electricity spreading through any chain of nails. After all unions, compare each nail’s representative with the last segment’s representative.
4. In the sample, the slanted wire touches the vertical nail at x=3 and the horizontal nail at y=3. These form the live component. The high horizontal nail and the separate slanted nail are disconnected from it, so two nails are safe.

Why it works

The closed-segment test is exact by bounding-box overlap and mutual orientation conditions, including degenerate and collinear segments. DSU merges precisely the endpoints of every edge in the segment-contact graph. Its final sets are therefore exactly that graph’s connected components. Electricity reaches exactly the wire’s component, so counting nails outside it gives the safe total.

Watch out. The input contains no N: read until EOF, then take the last segment as the wire. A nail need not touch the wire directly to be unsafe. Include endpoint and collinear contact. Use integer cross products, not floating-point line slopes.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<numeric>
#include<algorithm>
using namespace std;
struct Point{
    long long x,y;
};
struct Segment{
    Point first,second;
};
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);
}
bool oppositeOrZero(long long a,long long b){
    return a==0||b==0||(a<0)!=(b<0);
}
bool intersects(const Segment&a,const Segment&b){
    if(max(a.first.x,a.second.x)<min(b.first.x,b.second.x)||
        max(b.first.x,b.second.x)<min(a.first.x,a.second.x)||
        max(a.first.y,a.second.y)<min(b.first.y,b.second.y)||
        max(b.first.y,b.second.y)<min(a.first.y,a.second.y)){
        return false;
    }
    return oppositeOrZero(cross(a.first,a.second,b.first),cross(a.first,a.second,b.second))&&
        oppositeOrZero(cross(b.first,b.second,a.first),cross(b.first,b.second,a.second));
}
int findRoot(vector<int>&parent,int vertex){
    if(parent[vertex]!=vertex){
        parent[vertex]=findRoot(parent,parent[vertex]);
    }
    return parent[vertex];
}
int main(){
    vector<Segment>segments;
    Segment segment;
    while(cin>>segment.first.x>>segment.first.y>>segment.second.x>>segment.second.y){
        segments.push_back(segment);
    }
    if(segments.empty()){
        return 0;
    }
    int count=static_cast<int>(segments.size());
    vector<int>parent(count),size(count,1);
    iota(parent.begin(),parent.end(),0);
    for(int first=0;first<count;++first){
        for(int second=first+1;second<count;++second){
            if(!intersects(segments[first],segments[second])){
                continue;
            }
            int a=findRoot(parent,first);
            int b=findRoot(parent,second);
            if(a!=b){
                if(size[a]<size[b]){
                    swap(a,b);
                }
                // Every contact joins the entire conductive components.
                parent[b]=a;
                size[a]+=size[b];
            }
        }
    }
    int live=findRoot(parent,count-1);
    int safe=0;
    for(int nail=0;nail+1<count;++nail){
        if(findRoot(parent,nail)!=live){
            ++safe;
        }
    }
    cout<<safe<<'\n';
}