Advertisement
Guest User

Untitled

a guest
Dec 21st, 2014
166
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.77 KB | None | 0 0
  1. #include <cstdlib>
  2. #include <iostream>
  3. #include <stdio.h>
  4. #include <cstring>
  5. #include <vector>
  6. #include <algorithm>
  7. #include <utility>
  8. #include <queue>
  9. #include <map>
  10. #include <stack>
  11. #include <cmath>
  12. #include <set>
  13. #include <ctype.h>
  14. #include <bitset>
  15.  
  16. #define INF 0x3F3F3F3F
  17. #define rep(i, a, b) for (int i = int(a); i < int(b); i++)
  18. #define TRvii(c, it) for (vii::iterator it = (c).begin(); it != (c).end(); it++)
  19. #define tr(it, s)  for ( typeof ( s.begin( ) ) it=s.begin( ); it!=s.end( ); it++ )
  20. #define pb push_back
  21. #define clr(a) memset((a),0,sizeof(a))
  22. #define pi 3.1415926535897932384626433832795028841971
  23. #define debug(x) cout << #x << " = " << x << endl;
  24. #define debug2(x,y) cout << #x << " = " << x << " --- " << #y << " " << y << "\n";
  25. #define all(S) (S).begin(), (S).end()
  26. #define MAXV 1005
  27. #define F first
  28. #define S second
  29. #define EPS 1e-9
  30.  
  31. using namespace std;
  32.  
  33. typedef long long ll;
  34. typedef pair < int, int >  ii;
  35. typedef vector < int >  vi;
  36. typedef vector < ii >  vii;
  37.  
  38. struct point{    
  39.     double x, y;
  40.     point (double _x=0, double _y=0) : x(_x), y(_y) {};
  41.    
  42.     point operator -(point q) { return point( x-q.x, y-q.y); }
  43.     double operator %(point q) { return x*q.y - y*q.x; }
  44. };
  45.  
  46. double ccw(point i, point j, point k){
  47.     point U = j-i, V = k-i; double ans = U % V;
  48.     return ans;
  49. }
  50.  
  51. double dist_pt(point a, point b){
  52.     return sqrt((b.x-a.x)*(b.x-a.x) + (b.y-a.y)*(b.y-a.y));
  53. }
  54.  
  55.  
  56. int n;
  57. point p[101];
  58.  
  59. int main(){
  60.  
  61.     int x, y;
  62.     double sn, sp, ans;
  63.    
  64.     while(scanf("%d",&n) && n){
  65.        
  66.             rep(i,0,n){
  67.                 scanf("%d%d",&x,&y);  
  68.                 p[i].x = x; p[i].y = y;
  69.             }
  70.            
  71.             ans = INF;
  72.            
  73.             point a, b, r;
  74.            
  75.             rep(i,0,n){  
  76.                    a.x = p[i].x; a.y = p[i].y;
  77.                    rep(j,i+1,n){  
  78.                         b.x = p[j].x; b.y = p[j].y;
  79.                         sn = sp = 0;
  80.                         rep(k,0,n){
  81.    
  82.                             r.x = p[k].x; r.y = p[k].y;
  83.                            
  84.                             double area = ccw(a, b, r);                          
  85.                             double base = dist_pt(a,b);          
  86.                             double alt = area/base;                        
  87.                            
  88.                             if(area < 0) sn += alt;
  89.                             else if(area > 0) sp += alt;    
  90.                                                  
  91.                         }    
  92.                        
  93.                         ans = min(ans, abs(sn+sp));                                    
  94.                    }
  95.             }
  96.            
  97.             printf("%.3lf\n",ans);
  98.     }
  99.  
  100.     return 0;
  101. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement