CSES - Siperia opettaa 2.0 - Results
Submission details
Task:Lines
Sender:Hansuzu
Submission time:2016-07-30 14:51:21 +0300
Language:C++
Status:COMPILE ERROR

Compiler report

input/code.cpp: In function 'long long int ibm(double)':
input/code.cpp:62:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i+1<xs.size(); i+=2){
                             ^
input/code.cpp:69:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i+1<pts.size(); i+=2){
                              ^
input/code.cpp:77:52: error: expected ']' before ')' token
   if (pts.size()%2) sm+=get(0, ix[pts[pts.size()-1]);
                                                    ^
input/code.cpp:77:34: error: no match for 'operator[]' (operand types are 'std::unordered_map<double, int>' and '__gnu_cxx::__alloc_traits<std::allocator<std::pair<std::pair<double, double>, int> > >::value_type {aka std::pair<std::pair<double, double>, int>}')
   if (pts.size()%2) sm+=get(0, ix[pts[pts.size()-1]);
                                  ^
input/code.cpp:77:34: note: candidates are:
In file included from...

Code

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#include <unordered_map>
#define MP make_pair
#define F first
#define S second
#define SZ (1<<18)
using namespace std;
int n;

double cot(double a){
  double d=tan(a);
  if (d!=d) return 0;
  else return 1l/d;
}

int sp[SZ];

void put(int a){a+=SZ/2;
  sp[a]+=1;
  for (a/=2; a; a/=2) sp[a]=sp[2*a]+sp[2*a+1];
}

int get(int a, int b){a+=SZ/2; b+=SZ/2;
  int rv=0;
  while (a<b){
    if (a%2==1) rv+=sp[a++];
    if (b%2==0) rv+=sp[b--];
    a/=2; b/=2;
  }if (a==b) rv+=sp[a];
  return rv;
}


double PI=-1;


int x[101010];
int y[101010];

vector<pair<pair<double, double>, int> > pts;

vector<double> xs;
unordered_map<double, int> ix;

long long ibm(double ang){
  for (int i=0; i<SZ; i+=2) sp[i]=0, sp[i+1]=0;
  xs.clear();
  ix.clear();
  double k=cot(ang);
  for (int i=0; i+1<n; i+=2){
    xs.push_back(pts[i].F.S=x[pts[i].S]-k*pts[i].F.F);
    xs.push_back(pts[i+1].F.S=x[pts[i+1].S]-k*pts[i+1].F.F);
  }
  if (n%2) xs.push_back(pts[n-1].F.S=x[pts[n-1].S]-k*pts[n-1].F.F);
  
  sort(xs.begin(), xs.end());
  
  for (int i=0; i+1<xs.size(); i+=2){
    ix[xs[i]]=i;
    ix[xs[i+1]]=i+1;
  }
  if (xs.size()%2) ix[xs[xs.size()-1]]=xs.size()-1;
  
  long long sm=0;
  for (int i=0; i+1<pts.size(); i+=2){
    int ii=ix[pts[i].F.S];
    sm+=get(0, ii);;
    put(ii);
    int ii2=ix[pts[i+1].F.S];
    sm+=get(0, ii2);;
    put(ii2);
  }
  if (pts.size()%2) sm+=get(0, ix[pts[pts.size()-1]);
  return sm;
}


double bin(long long v){
  double a=0;
  double b=PI;
  for (int i=0; i<35; ++i){
    double m=(a+b)/2;
    if (ibm(m)>=v) b=m;
    else a=m;
  }
  return (a+b)/2;
}

int main(){
  PI=acos(PI);
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n;
  for (int i=0; i<n; ++i) cin >> x[i] >> y[i];
  for (int i=0; i<n; ++i) pts.push_back(MP(MP(y[i], x[i]), i));
  sort(pts.begin(), pts.end());
  double a=bin(((long long)n*(n-1)/2+1)/2);
  double b=bin(((long long)n*(n-1)/2+2)/2);
  cout << setprecision(20) << (a+b)/2 << "\n";
}