Geometry

#include<bits/stdc++.h>
using namespace std;
#define   MP             make_pair
#define   PB             push_back
#define   nn             '\n'
#define   endl           '\n'
#define   IOS            ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define   UNIQUE(vec)    vec.resize(distance(vec.begin(),unique(vec.begin(),vec.end()))) ;
#define   all(vec)       vec.begin(),vec.end()
#define   int            long long
#define   pii            pair<int,int>
#define   pdd            pair<double,double>

typedef long long LL ;

const int MOD=1e9+7,Base=998244353 ;
const int N=1e6+7 ;
const int INF=1LL*1000*1000*1000*1000*1000*1000+7LL, INF2=(1LL<<62) ;
const double pie=acos(-1.0) ;
const double EPS=1e-9 ;

double w , h , a ;

struct line
{
    double a , b , c ;
    line(){}
    line(pdd A , pdd B)
    {
    a = B.second - A.second;
    b = A.first - B.first;
    c = a*(A.first) + b*(A.second);
    c = -c ;  /// ax + by + c = 0 format
    }
};

pdd LineLineIntersection(line A, line B){
    /// Line AB represented as a1x + b1y = c1
    double a1 = A.a ;
    double b1 = A.b ;
    double c1 = -A.c ;

    /// Line CD represented as a2x + b2y = c2
    double a2 = B.a ;
    double b2 = B.b ;
    double c2 = -B.c ;

    double determinant = a1*b2 - a2*b1;

    if (determinant == 0){
        // The lines are parallel. This is simplified
        // by returning a pair of FLT_MAX
        return make_pair(INF, INF);
    }
    else{
        double x = (b2*c1 - b1*c2)/determinant;
        double y = (a1*c2 - a2*c1)/determinant;
        return make_pair(x, y);
    }
}

double Radian(double x){
    return x*pie/180.0 ;
}



/*
/// angle of a point considering origin at (0,0) 
double angle(pt p)
{
    if(abs(p.x)<EPS){
            if(p.y<0.0)
                return 270.0 ;
            return 90.0 ;
    }
    double ang = atan(abs(p.y)/abs(p.x)) ;
    ang = ang*180.0/pie ;
    if(p.x<0.0)
    {
        if(p.y>=0.0)
            ang = 180.0-ang ;
        else
            ang = 180.0+ang ;
    }
    else
    {
        if(p.y<0.0)
        ang = 360.0 - ang ;
    }
    return ang ;
}
/**/



pdd RotatePoint(pdd p, pdd o,double ang)
{
  double s = sin(Radian(ang)) ;
  double c = cos(Radian(ang)) ;

  /// translate point back to origin:
  p.first -= o.first ;
  p.second -= o.second ;

  /// rotate point
  double xnew = p.first * c - p.second * s ;
  double ynew = p.first * s + p.second * c ;

  /// translate point back:
  p.first = xnew + o.first ;
  p.second = ynew + o.second ;
  return p ;
}

double Area(vector<pdd>pts) ;
vector<pdd>Sort(vector<pdd>pts) ;

int32_t main()
{
    IOS

    double w , h , ang ;

    cin>>w>>h>>ang ;

    if(ang==180.0 or ang==360.0)
    ang=0.0 ; 
    
    //if(w<h)swap(w,h) ;

    w=.5*w ; h=.5*h ;

    vector<pdd>pa , pb ;

    vector<line>la , lb ;

    pa.PB({w,h}) ;
    pa.PB({-w,h}) ;
    pa.PB({-w,-h}) ;
    pa.PB({w,-h}) ;

    for(int i=0;i<4;++i)
    {
        pb.PB(RotatePoint(pa[i],{0.0,0.0},ang)) ;
    }

    for(int i=0;i<4;++i)
    {
        la.PB(line(pa[i],pa[(i+1)%4])) ;
        lb.PB(line(pb[i],pb[(i+1)%4])) ;
    }

    vector<pdd>pts ;

    for(line La:la)
    {
        for(line Lb:lb)
        {
            pdd p=LineLineIntersection(La,Lb) ;
            if(p.first==INF)continue ;
            if(abs(p.first)<=w and abs(p.second)<=h)
                pts.PB(p) ;
        }
    }

    pts=Sort(pts) ;
/**
    for(pdd p:pts)
        cout<<p.first<<' '<<p.second<<endl ;
/**/
    cout<<setprecision(10)<<fixed<<Area(pts)<<endl ;

    return 0 ;
}

vector<pdd>Sort(vector<pdd>pts)
{
    vector<pdd>ng , pg ;

    for(pdd p:pts)
    {
        if(p.second<0.0)
            ng.PB(p) ;
        else
            pg.PB(p) ;
    }

    sort(all(ng)) ;

    sort(all(pg)) ;

    reverse(all(pg)) ;

    for(int i=0;i<pg.size();++i)
        ng.PB(pg[i]) ;

    return ng ;
}

double Area(vector<pdd>pts)
{
   pts.PB(pts[0]) ;
   double a=0 ;

   for(int i=0;i<pts.size()-1;++i)
    a+=pts[i].first*pts[i+1].second-pts[i].second*pts[i+1].first ;

   a=a*.5 ; return abs(a) ;
}

https://codeforces.com/problemset/problem/406/D /// convex hull graham scan + lca used  

int n, m, stk[N], d[N], anc[N][20] ;

pii pt[N] ;

int area(pii a ,pii b, pii c)
{
    return a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x ;
}

int lca(int u,int v)
{
    //cout<<" u "<<u<<" v "<<v<<endl ;
    if(d[u]<d[v])
        swap(u,v) ;
    for(int j=19;j>=0 and d[u]>d[v] ;--j)  /// u niche ...
    {
        if(anc[u][j]==0)continue ;
        if(d[anc[u][j]]>=d[v])
            u=anc[u][j] ;
    }
    //cout<<" same level "<<u<<" "<<v<<endl ;
    for(int j=19;j>=0 and u!=v; --j)
    {
        if(anc[u][j]!=anc[v][j])
            u=anc[u][j], v=anc[v][j] ;
        u=anc[u][0], v=anc[v][0] ;
    }
    return u ;
}

int32_t main()
{
    IOS

    cin>>n ;

    for(int i=1; i<=n; ++i)
    {
        cin>>pt[i].x>>pt[i].y ;
    }

    anc[0][n]=0 ;

    int top = 0 ;

    for(int i=n; i>=1; --i)
    {
        while(top>=2 and area(pt[i],pt[stk[top]],pt[stk[top-1]])>0)--top ;

        if(top)
        {
            anc[i][0]=stk[top] ;
            //cout<<" i "<<i<<" top "<<stk[top]<<endl ;
            d[i]=d[stk[top]]+1 ;
            for(int j=1,md; j<20; ++j)
            {
                md = anc[i][j-1] ;
                anc[i][j] = anc[md][j-1] ;
            }
        }

        stk[++top]=i ;
    }



/// closest pair points 
/// https://codeforces.com/problemset/problem/429/D

#include<bits/stdc++.h>
using namespace std;
#define   MP             make_pair
#define   PB             push_back
#define   nn             '\n'
#define   IOS            ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define   UNIQUE(vec)    vec.resize(distance(vec.begin(),unique(vec.begin(),vec.end()))) ;
#define   ClearVec(vec)  while(vec.size())vec.pop_back()
#define   ALL(vec)       vec.begin(),vec.end()
#define   int            long long

typedef long long LL ;

const int MOD=1e9+7,Base=998244353 ;
const int N=1e6+7 ;
const int INF=1LL*1000*1000*1000*1000*1000*1000+7LL, INF2=(1LL<<62) ;
const double pie=acos(-1.0) ;
const double EPS=1e-9 ;

int n, a[N] ;

pair<int,int>p[N] ;

int sq(int x)
{
    return x*x ; 
}

int dist(int i,int j){
    return (p[i].first-p[j].first)*(p[i].first-p[j].first)+(p[i].second-p[j].second)*(p[i].second-p[j].second) ;
}

int Dist(pair<int,int>a,pair<int,int>b)
{
    return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second) ;
}

bool cmpx(pair<int,int>a,pair<int,int>b)
{
    if(a.first==b.first)
        return a.second<b.second ;

    return a.first<b.first ;
}

bool cmpy(pair<int,int>a,pair<int,int>b)
{
    if(a.second==b.second)
        return a.first<b.first ;

    return a.second<b.second ;
}

int Closest_Pair(int low,int high)
{
    if(high-low<=5)
    {
        int Min=INF ;

        for(int i=low;i<=high;++i)
        for(int j=i+1;j<=high;++j)
        Min=min(Min,dist(i,j)) ;

        return Min ;
    }

    int mid=(high+low)>>1 , d ;

    d=min(Closest_Pair(low,mid),Closest_Pair(mid+1,high)) ;

    vector<pair<int,int>>vec ;

    for(int i=low;i<=high;++i)
    {
        if(sq(p[i].first-p[mid].first)<=d)
        {
            vec.PB(p[i]) ;
        }
    }

    sort(ALL(vec),cmpy) ;

    for(int i=0;i<vec.size();++i)
    {
        for(int j=i+1;j<=i+7 and j<vec.size();++j)
        {
           d=min(Dist(vec[i],vec[j]),d) ;
        }
    }

    return d ;
}

int32_t main()
{
    IOS ;

    cin>>n ;

    for(int i=1 , sum=0 ; i<=n; ++i)
        cin>>a[i] , sum+=a[i] , p[i]={i,sum} ;

    sort(p+1,p+n+1,cmpx) ;

    cout<<Closest_Pair(1,n) ;

    return 0;
}

/// circle line intersection ... 
/// from shahjalal shohag ... 
/**

const int N = 3e5 + 9;

const double inf = 1e100;
const double eps = 1e-9;
const double PI = acos((double)-1.0);
int sign(double x) { return (x > eps) - (x < -eps); }

struct PT {
    double x, y;
    PT() { x = 0, y = 0; }
    PT(double x, double y) : x(x), y(y) {}
    PT(const PT &p) : x(p.x), y(p.y)    {}
    PT operator + (const PT &a) const { return PT(x + a.x, y + a.y); }
    PT operator - (const PT &a) const { return PT(x - a.x, y - a.y); }
    PT operator * (const double a) const { return PT(x * a, y * a); }
    friend PT operator * (const double &a, const PT &b) { return PT(a * b.x, a * b.y); }
    PT operator / (const double a) const { return PT(x / a, y / a); }
    bool operator == (PT a) const { return sign(a.x - x) == 0 && sign(a.y - y) == 0; }
    bool operator != (PT a) const { return !(*this == a); }
    bool operator < (PT a) const { return sign(a.x - x) == 0 ? y < a.y : x < a.x; }
    bool operator > (PT a) const { return sign(a.x - x) == 0 ? y > a.y : x > a.x; }
    double norm() { return sqrt(x * x + y * y); }
    double norm2() { return x * x + y * y; }
    PT perp() { return PT(-y, x); }
    double arg() { return atan2(y, x); }
    PT truncate(double r) { // returns a vector with norm r and having same direction
        double k = norm();
        if (!sign(k)) return *this;
        r /= k;
        return PT(x * r, y * r);
    }
};

inline double dot(PT a, PT b){ return a.x * b.x + a.y * b.y; }

vector<PT> circle_line_intersection(PT c, double r, PT a, PT b) {
    vector<PT> ret;
    b = b - a; a = a - c;
    double A = dot(b, b), B = dot(a, b);
    double C = dot(a, a) - r * r, D = B * B - A * C;
    if (D < -eps) return ret;
    ret.push_back(c + a + b * (-B + sqrt(D + eps)) / A);
    if (D > eps) ret.push_back(c + a + b * (-B - sqrt(D)) / A);
    return ret;
}