Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdlib>
- #include <iostream>
- #include <stdio.h>
- #include <cstring>
- #include <vector>
- #include <algorithm>
- #include <utility>
- #include <queue>
- #include <map>
- #include <stack>
- #include <cmath>
- #include <set>
- #include <ctype.h>
- #include <bitset>
- #define INF 0x3F3F3F3F
- #define rep(i, a, b) for (int i = int(a); i < int(b); i++)
- #define TRvii(c, it) for (vii::iterator it = (c).begin(); it != (c).end(); it++)
- #define tr(it, s) for ( typeof ( s.begin( ) ) it=s.begin( ); it!=s.end( ); it++ )
- #define pb push_back
- #define clr(a) memset((a),0,sizeof(a))
- #define pi 3.1415926535897932384626433832795028841971
- #define debug(x) cout << #x << " = " << x << endl;
- #define debug2(x,y) cout << #x << " = " << x << " --- " << #y << " " << y << "\n";
- #define all(S) (S).begin(), (S).end()
- #define MAXV 1005
- #define F first
- #define S second
- #define EPS 1e-9
- using namespace std;
- typedef long long ll;
- typedef pair < int, int > ii;
- typedef vector < int > vi;
- typedef vector < ii > vii;
- struct point{
- double x, y;
- point (double _x=0, double _y=0) : x(_x), y(_y) {};
- point operator -(point q) { return point( x-q.x, y-q.y); }
- double operator %(point q) { return x*q.y - y*q.x; }
- };
- double ccw(point i, point j, point k){
- point U = j-i, V = k-i; double ans = U % V;
- return ans;
- }
- double dist_pt(point a, point b){
- return sqrt((b.x-a.x)*(b.x-a.x) + (b.y-a.y)*(b.y-a.y));
- }
- int n;
- point p[101];
- int main(){
- int x, y;
- double sn, sp, ans;
- while(scanf("%d",&n) && n){
- rep(i,0,n){
- scanf("%d%d",&x,&y);
- p[i].x = x; p[i].y = y;
- }
- ans = INF;
- point a, b, r;
- rep(i,0,n){
- a.x = p[i].x; a.y = p[i].y;
- rep(j,i+1,n){
- b.x = p[j].x; b.y = p[j].y;
- sn = sp = 0;
- rep(k,0,n){
- r.x = p[k].x; r.y = p[k].y;
- double area = ccw(a, b, r);
- double base = dist_pt(a,b);
- double alt = area/base;
- if(area < 0) sn += alt;
- else if(area > 0) sp += alt;
- }
- ans = min(ans, abs(sn+sp));
- }
- }
- printf("%.3lf\n",ans);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement