fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct Point{long double px,py;};
  4. long double dot(const Point& a,const Point& b){
  5. 	return a.px*b.px+a.py*b.py;
  6. }
  7. long double crs(const Point& a,const Point& b){
  8. 	return a.px*b.py-a.py*b.px;
  9. }
  10. long double norm(const Point& a){
  11. 	return a.px*a.px+a.py*a.py;
  12. }
  13. int ccw(Point p0,Point p1,Point p2){
  14. 	Point a,b;
  15. 	a.px=p1.px-p0.px;
  16. 	a.py=p1.py-p0.py;
  17. 	b.px=p2.px-p0.px;
  18. 	b.py=p2.py-p0.py;
  19. 	if(crs(a,b)>1e-10)return 1;
  20. 	if(crs(a,b)<-1e-10)return -1;
  21. 	if(dot(a,b)<-1e-10)return 2;
  22. 	if(norm(a)<norm(b))return -2;
  23. 	return 0;
  24. }
  25. bool its(Point p1,Point p2,Point p3,Point p4){
  26. 	return ((ccw(p1,p2,p3)*ccw(p1,p2,p4)<=0)&&(ccw(p3,p4,p1)*ccw(p3,p4,p2)<=0));
  27. }
  28. int n;Point D[3000];vector<pair<int,int>>K;
  29. int main(){
  30. 	cin>>n;
  31. 	for(int i=0;i<n;i++){
  32. 		cin>>D[i].px>>D[i].py;
  33. 	}
  34. 	for(int i=0;i<n;i++){
  35. 		for(int j=i+1;j<n;j++){
  36. 			bool ok=true;
  37. 			for(int k=0;k<K.size();k++){
  38. 				if(i==K[k].first||j==K[k].second){continue;}
  39. 				if(j==K[k].first||i==K[k].second){continue;}
  40. 				if(its(D[K[k].first],D[K[k].second],D[i],D[j])==1){ok=false;}
  41. 			}
  42. 			if(ok==true){K.push_back(make_pair(i,j));}
  43. 		}
  44. 	}
  45. 	cout<<K.size()<<endl;
  46. 	return 0;
  47. }
  48.  
Success #stdin #stdout 0s 3488KB
comments (?)
stdin
copy 
4
0 0
1 1
0 1
1 0
stdout
copy 
5
https://ideone.com/IcwN77
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!