Dots
National Olympiad — Municipal round (2012 season)
Submission name: dots.cpp
Problem summary
Given four points, draw all segments between distinct marked points and cut along them. Count the triangular bounded pieces produced, accounting for coincident and collinear points.
Input
Four lines, each with integer x y.
Output
The number of triangular pieces.
Constraints
−100 ≤ x,y ≤ 100; the four points may coincide.
Worked example
Official statement sample.
Input
-1 -1 3 2 1 4 -3 3
Output
4
Solution analysis
- First remove duplicate points. With fewer than three distinct points there is no bounded piece. With exactly three, the answer is one unless all three are collinear.
- For four distinct points, count nondegenerate triples. If there are none the points are collinear. If there are exactly three, one point lies on a side of the triangle formed by the others; the segments split that triangle into two triangular pieces.
- Otherwise no three are collinear. Test whether one point lies strictly inside the triangle formed by the other three. An interior point creates three triangular pieces; if no point is interior, the four points form a convex quadrilateral whose diagonals create four pieces, as in the first sample.
Why it works
The cases exhaust all configurations of at most four distinct points. In the collinear-side case the only interior cut joins the side point to the opposite vertex, producing two triangles. In general position the convex hull has either three or four vertices, and the complete segment drawing produces respectively three or four triangular bounded faces.
Watch out. Count actual pieces rather than all triangles formed by segments. Remove repeated coordinates before classifying.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct Point{
int x,y;
bool operator<(const Point&other)const{
return x!=other.x?x<other.x:y<other.y;
}
bool operator==(const Point&other)const{
return x==other.x&&y==other.y;
}
};
int 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(){
vector<Point>p(4);
for(Point&v:p){
cin>>v.x>>v.y;
}
sort(p.begin(),p.end());
p.erase(unique(p.begin(),p.end()),p.end());
int n=p.size();
// Count noncollinear triples to distinguish degenerate configurations.
int triples=0;
for(int i=0;i<n;++i){
for(int j=i+1;j<n;++j){
for(int k=j+1;k<n;++k){
triples+=cross(p[i],p[j],p[k])!=0;
}
}
}
int answer=0;
if(n==3&&triples){
answer=1;
}
if(n==4&&triples==3){
answer=2;
}
if(n==4&&triples==4){
answer=4;
for(int i=0;i<4;++i){
vector<Point>t;
for(int j=0;j<4;++j){
if(j!=i){
t.push_back(p[j]);
}
}
int a=cross(t[0],t[1],p[i]);
int b=cross(t[1],t[2],p[i]);
int c=cross(t[2],t[0],p[i]);
if((a>0&&b>0&&c>0)||(a<0&&b<0&&c<0)){
answer=3;
}
}
}
cout<<answer<<'\n';
}