Submission #2118312


Source Code Expand

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;

#define pb push_back
#define fr first
#define sc second

const long double EPS = 0.00000000001;

struct BIT{
	int siz;
	int a[(1<<16)+10];
	void init(int siz_ = 1<<16){
		siz = siz_;
		for(int i = 1 ; i <= siz ; i ++){
			a[i] = 0;
		}
	}
	void add(int k,int x = 1){
		while(k <= siz){
			a[k] += x;
			k += k&-k;
		}
	}
	int sum(int k){
		int ret = 0;
		while(k > 0){
			ret += a[k];
			k -= k&-k;
		}
		return ret;
	}
}bit;

int N;
long double A[40002];
long double B[40002];
long double C[40002];

int inv(vector<pair<long double,long double>> *vec){
	/*for(int i = 0 ; i < vec->size() ; i ++){
		cout << (*vec)[i].fr << " " << (*vec)[i].sc << endl;
	}*/
	
	vector<pair<long double,int>> a;
	for(int i = 0 ; i < vec->size() ; i ++){
		a.pb(pair<long double,int>((*vec)[i].sc,i+1));
	}
	sort(a.begin(),a.end());
	int ret = 0;
	bit.init();
	for(int i = 0 ; i < a.size() ; i ++){
		ret += bit.sum(a[i].sc);
		bit.add(a[i].sc);
	}
	return N*(N-1)/2-ret;
}

long double sol(){
	long double l = -200000000.0 , r = 200000000.0;
	while(l+EPS < r){
		long double m = (l+r)/2.0;
		vector<pair<long double,long double>> vec;
		for(int i = 1 ; i <= N ; i ++){
			vec.pb(pair<long double,long double>((C[i]-A[i]*m)/B[i],-A[i]/B[i]));
		}
		sort(vec.begin(),vec.end());
		if(inv(&vec)*2 <= N*(N-1)/2)r = m;
		else l = m;
	}
	return l;
}

int main(){
	cout.precision(20);
	
	scanf("%d",&N);
	for(int i = 1 ; i <= N ; i ++){
		cin >> A[i] >> B[i] >> C[i];
	}
	long double X = sol();
	
	for(int i = 1 ; i <= N ; i ++){
		swap(A[i],B[i]);
	}
	long double Y = sol();
	
	cout << X << " " << Y << endl;
}

Submission Info

Submission Time
Task E - CARtesian Coodinate
User yokozuna57
Language C++14 (GCC 5.4.1)
Score 800
Code Size 1874 Byte
Status AC
Exec Time 1737 ms
Memory 8920 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:86:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
                ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 800 / 800
Status
AC × 3
AC × 35
Set Name Test Cases
Sample s1.txt, s2.txt, s3.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt AC 1721 ms 6984 KB
02.txt AC 1710 ms 6984 KB
03.txt AC 1723 ms 6984 KB
04.txt AC 1737 ms 6984 KB
05.txt AC 1714 ms 6984 KB
06.txt AC 1714 ms 6984 KB
07.txt AC 1729 ms 6984 KB
08.txt AC 1706 ms 6984 KB
09.txt AC 1716 ms 6984 KB
10.txt AC 1709 ms 6984 KB
11.txt AC 1712 ms 7000 KB
12.txt AC 1720 ms 6984 KB
13.txt AC 1702 ms 6984 KB
14.txt AC 1710 ms 8920 KB
15.txt AC 1720 ms 6984 KB
16.txt AC 1716 ms 6984 KB
17.txt AC 1715 ms 6984 KB
18.txt AC 1707 ms 6984 KB
19.txt AC 1683 ms 8616 KB
20.txt AC 1710 ms 6984 KB
21.txt AC 1369 ms 6984 KB
22.txt AC 1359 ms 6984 KB
23.txt AC 1729 ms 6984 KB
24.txt AC 1678 ms 8616 KB
25.txt AC 1724 ms 6984 KB
26.txt AC 1735 ms 6984 KB
27.txt AC 5 ms 512 KB
28.txt AC 5 ms 512 KB
29.txt AC 5 ms 512 KB
30.txt AC 5 ms 512 KB
31.txt AC 5 ms 512 KB
32.txt AC 5 ms 512 KB
s1.txt AC 5 ms 512 KB
s2.txt AC 5 ms 512 KB
s3.txt AC 5 ms 512 KB