Ideone.com

download

copy

//============================================================================
// Name        : ICPC.cpp
// Author      : MaTb3aa
// Quotes      : Nothing is impossible, the word itself says 'I'm possible'!.
// Copyright   : Audrey Hepburn
// Description : You Can Do It
//============================================================================
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <cmath>
#include <stack>
#include <string>
#include <iomanip>
#include <queue>
#include <deque>
#include <cstring>
#include <limits>
#include <sstream>
#include <stdio.h>
#include<unordered_map>
#include <string>
#define ll_str(x,y) stringstream sdf;sdf<<x;string str=sdf.str();y=str;
#define str_ll(x,y) stringstream sstr(x);ll val;sstr>>val;y=val;
const int N = 1e6 + 5, M = 1e5 + 5, OO = 0x3f3f3f3f, mod = 1e9 + 7;
#define all(v) ((v).begin()), ((v).end())
int dx[] = { 0, 0, 1, -1, 1, -1, 1, -1 };
int dy[] = { 1, -1, 0, 0, -1, 1, 1, -1 };
#define mem(x,y) memset(x,y,sizeof(x))
using namespace std;
typedef long long ll;
#define endl '\n'
double PI = 3.14159265359;
ll gcd(ll x, ll y) { return (!y) ? x : gcd(y, x%y); }
ll lcm(ll x, ll y) { return ((x / gcd(x, y))*y); }
 
 
void file() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif // !ONLINEJUDGE
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}
double slope(int x1, int y1, int x2, int y2) {
	int m1 = (x2 - x1);
	int m2 = (y2 - y1);
	return (m1 == 0) ? -1 : m2 / m1*1.0 ;
}
vector<pair<int, int>>v;
bool ok(double m1, double m2,double slope,double intecept_y) {
	double y3 = slope * m1 + intecept_y;
	double y4 = slope * m2 + intecept_y;
	double sum1=0,sum2=0;
	for (int i = 0; i < v.size(); i++) {
		sum1 += sqrt(pow(y3 - v[i].second, 2) + pow(m1 - v[i].first, 2));
		sum2 += sqrt(pow(y4 - v[i].second, 2) + pow(m2 - v[i].first, 2));
	}
	return sum1 < sum2;
}
int main() {
	file();
	int n, x1, y1, x2, y2;
	cin >> n >> x1 >> y1 >> x2 >> y2;
	for (int i = 0; i < n; i++) {
		int x, y; cin >> x >> y;
		v.push_back({ x,y });
	}
	double s = slope(x1, y1, x2, y2);
	double intercept_y = y1 - s * x1;
	/* Ternary Search */
	double st = 0, ed =1000 , m1=-1, m2=-1;
	while (st-ed <= .000001) {
		m1 = st + (ed - st) / 3.0;
		m2 = ed - (ed - st) / 3.0;
		cout << m1 << endl;
		if (ok(m1, m2, s, intercept_y)) {
			ed = m2 + 1;
		}
		else
			st = m1  - 1;
	}
	//cout << st << " " << ed << " " << m1 << " " << m2 << endl;
 
	return 0;
}

Ly89PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci8vIE5hbWUgICAgICAgIDogSUNQQy5jcHAKLy8gQXV0aG9yICAgICAgOiBNYVRiM2FhCi8vIFF1b3RlcyAgICAgIDogTm90aGluZyBpcyBpbXBvc3NpYmxlLCB0aGUgd29yZCBpdHNlbGYgc2F5cyAnSSdtIHBvc3NpYmxlJyEuCi8vIENvcHlyaWdodCAgIDogQXVkcmV5IEhlcGJ1cm4KLy8gRGVzY3JpcHRpb24gOiBZb3UgQ2FuIERvIEl0Ci8vPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQojZGVmaW5lIF9DUlRfU0VDVVJFX05PX1dBUk5JTkdTCiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPG1hcD4KI2luY2x1ZGUgPHNldD4KI2luY2x1ZGUgPGJpdHNldD4KI2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8c3RhY2s+CiNpbmNsdWRlIDxzdHJpbmc+CiNpbmNsdWRlIDxpb21hbmlwPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDxkZXF1ZT4KI2luY2x1ZGUgPGNzdHJpbmc+CiNpbmNsdWRlIDxsaW1pdHM+CiNpbmNsdWRlIDxzc3RyZWFtPgojaW5jbHVkZSA8c3RkaW8uaD4KI2luY2x1ZGU8dW5vcmRlcmVkX21hcD4KI2luY2x1ZGUgPHN0cmluZz4KI2RlZmluZSBsbF9zdHIoeCx5KSBzdHJpbmdzdHJlYW0gc2RmO3NkZjw8eDtzdHJpbmcgc3RyPXNkZi5zdHIoKTt5PXN0cjsKI2RlZmluZSBzdHJfbGwoeCx5KSBzdHJpbmdzdHJlYW0gc3N0cih4KTtsbCB2YWw7c3N0cj4+dmFsO3k9dmFsOwpjb25zdCBpbnQgTiA9IDFlNiArIDUsIE0gPSAxZTUgKyA1LCBPTyA9IDB4M2YzZjNmM2YsIG1vZCA9IDFlOSArIDc7CiNkZWZpbmUgYWxsKHYpICgodikuYmVnaW4oKSksICgodikuZW5kKCkpCmludCBkeFtdID0geyAwLCAwLCAxLCAtMSwgMSwgLTEsIDEsIC0xIH07CmludCBkeVtdID0geyAxLCAtMSwgMCwgMCwgLTEsIDEsIDEsIC0xIH07CiNkZWZpbmUgbWVtKHgseSkgbWVtc2V0KHgseSxzaXplb2YoeCkpCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgbG9uZyBsb25nIGxsOwojZGVmaW5lIGVuZGwgJ1xuJwpkb3VibGUgUEkgPSAzLjE0MTU5MjY1MzU5OwpsbCBnY2QobGwgeCwgbGwgeSkgeyByZXR1cm4gKCF5KSA/IHggOiBnY2QoeSwgeCV5KTsgfQpsbCBsY20obGwgeCwgbGwgeSkgeyByZXR1cm4gKCh4IC8gZ2NkKHgsIHkpKSp5KTsgfQoKCnZvaWQgZmlsZSgpIHsKI2lmbmRlZiBPTkxJTkVfSlVER0UKCWZyZW9wZW4oImlucHV0LnR4dCIsICJyIiwgc3RkaW4pOwoJZnJlb3Blbigib3V0cHV0LnR4dCIsICJ3Iiwgc3Rkb3V0KTsKI2VuZGlmIC8vICFPTkxJTkVKVURHRQoJaW9zOjpzeW5jX3dpdGhfc3RkaW8oMCk7IGNpbi50aWUoMCk7IGNvdXQudGllKDApOwp9CmRvdWJsZSBzbG9wZShpbnQgeDEsIGludCB5MSwgaW50IHgyLCBpbnQgeTIpIHsKCWludCBtMSA9ICh4MiAtIHgxKTsKCWludCBtMiA9ICh5MiAtIHkxKTsKCXJldHVybiAobTEgPT0gMCkgPyAtMSA6IG0yIC8gbTEqMS4wIDsKfQp2ZWN0b3I8cGFpcjxpbnQsIGludD4+djsKYm9vbCBvayhkb3VibGUgbTEsIGRvdWJsZSBtMixkb3VibGUgc2xvcGUsZG91YmxlIGludGVjZXB0X3kpIHsKCWRvdWJsZSB5MyA9IHNsb3BlICogbTEgKyBpbnRlY2VwdF95OwoJZG91YmxlIHk0ID0gc2xvcGUgKiBtMiArIGludGVjZXB0X3k7Cglkb3VibGUgc3VtMT0wLHN1bTI9MDsKCWZvciAoaW50IGkgPSAwOyBpIDwgdi5zaXplKCk7IGkrKykgewoJCXN1bTEgKz0gc3FydChwb3coeTMgLSB2W2ldLnNlY29uZCwgMikgKyBwb3cobTEgLSB2W2ldLmZpcnN0LCAyKSk7CgkJc3VtMiArPSBzcXJ0KHBvdyh5NCAtIHZbaV0uc2Vjb25kLCAyKSArIHBvdyhtMiAtIHZbaV0uZmlyc3QsIDIpKTsKCX0KCXJldHVybiBzdW0xIDwgc3VtMjsKfQppbnQgbWFpbigpIHsKCWZpbGUoKTsKCWludCBuLCB4MSwgeTEsIHgyLCB5MjsKCWNpbiA+PiBuID4+IHgxID4+IHkxID4+IHgyID4+IHkyOwoJZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKCQlpbnQgeCwgeTsgY2luID4+IHggPj4geTsKCQl2LnB1c2hfYmFjayh7IHgseSB9KTsKCX0KCWRvdWJsZSBzID0gc2xvcGUoeDEsIHkxLCB4MiwgeTIpOwoJZG91YmxlIGludGVyY2VwdF95ID0geTEgLSBzICogeDE7CgkvKiBUZXJuYXJ5IFNlYXJjaCAqLwoJZG91YmxlIHN0ID0gMCwgZWQgPTEwMDAgLCBtMT0tMSwgbTI9LTE7Cgl3aGlsZSAoc3QtZWQgPD0gLjAwMDAwMSkgewoJCW0xID0gc3QgKyAoZWQgLSBzdCkgLyAzLjA7CgkJbTIgPSBlZCAtIChlZCAtIHN0KSAvIDMuMDsKCQljb3V0IDw8IG0xIDw8IGVuZGw7CgkJaWYgKG9rKG0xLCBtMiwgcywgaW50ZXJjZXB0X3kpKSB7CgkJCWVkID0gbTIgKyAxOwoJCX0KCQllbHNlCgkJCXN0ID0gbTEgIC0gMTsKCX0KCS8vY291dCA8PCBzdCA8PCAiICIgPDwgZWQgPDwgIiAiIDw8IG0xIDw8ICIgIiA8PCBtMiA8PCBlbmRsOwoKCXJldHVybiAwOwp9

Runtime error #stdin #stdout 0s 15240KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/6aEIdc

language:

C++14 (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language