Submission #153696

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
153696	2019-09-15T08:19:18 Z	junodeveloper	2circles (balkan11_2circles)	C++14	Compilation error	0 ms	0 KB

twocircles

#include "bits/stdc++.h"
#define SZ(x) ((int)x.size())
using namespace std;
struct point {
	double x, y;
	point() {}
	point(double x, double y) : x(x), y(y) {}
	bool operator<(const point& b) const {
		return x == b.x ? y < b.y : x < b.x;
	}
};
struct Line {
	point s, t;
	Line() {}
	Line(point s, point t) : s(s), t(t) {}
};
double cross(point& a, point& b, point& c) {
	return (b.x - a.x) * (c.y - b.y) - (c.x - b.x) * (b.y - a.y);
}
double dirCross(Line& a, Line& b) {
	return (a.t.y - a.s.y) * (b.t.x - b.s.x) - (b.t.y - b.s.y) * (a.t.x - a.s.x);
}
point getIntersect(Line& a, Line& b) {
	double det = dirCross(a, b);
	double dx = b.s.x - a.s.x;
	double dy = b.s.y - a.s.y;
	double v = (-(b.t.y - b.s.y) * dx + (b.t.x - b.s.x) * dy) / det;
	return point(a.s.x + v * (a.t.x - a.s.x), a.s.y + v * (a.t.y - a.s.y));
}
bool isIncluded(Line& ln, point p) {
	return cross(ln.s, ln.t, p) >= 0;
}
bool bad(line& a, line& b, line& c) {
	point v;
	if(!line_intersect(a.s,a.t,b.s,b.t,v)) return 0;
	ld crs = (c.t.x-c.s.x)*(v.y-c.s.y)-(c.t.y-c.s.y)*(v.x-c.s.x);
	return crs < 0 || equals(crs, 0);
}

vector<point> HPI(vector<line>& ln) {
	deque<line> dq;
	for(int i=0; i<SZ(ln); i++) {
		while(dq.size() >= 2 && bad(dq[dq.size()-2], dq.back(), ln[i]))
			dq.pop_back();
		while(dq.size() >= 2 && bad(dq[0], dq[1], ln[i]))
			dq.pop_front();
		if(dq.size() < 2 || !bad(dq.back(), ln[i], dq[0]))
			dq.push_back(ln[i]);
	}
	vector<point> res;
	if(dq.size() >= 3) for(int i=0; i<sz(dq); i++) {
		int j=(i+1)%sz(dq);
		point v;
		if(!line_intersect(dq[i].s, dq[i].t, dq[j].s, dq[j].t, v)) continue;
		res.push_back(v);
	}
	return res;
}
double calipers(vector<point>& ch) {
	double mn = 9e18, mx = -9e18, res = 0;
	int lm, rm;
	for(int i=0; i<SZ(ch); i++) {
		if(mn > ch[i].x) mn = ch[i].x, lm = i;
		if(mx < ch[i].x) mx = ch[i].x, rm = i;
	}
	int i1 = lm, i2 = rm;
	while(i1 != rm || i2 != lm) {
		res = max(res, hypot(ch[i1].x - ch[i2].x, ch[i1].y - ch[i2].y));
		if(i1 == rm) i2 = (i2 + 1) % SZ(ch);
		else if(i2 == lm) i1 = (i1 + 1) % SZ(ch);
		else {
			int ni1 = (i1 + 1) % SZ(ch);
			int ni2 = (i2 + 1) % SZ(ch);
			if((ch[ni1].y - ch[i1].y) * (ch[ni2].x - ch[i2].x) >
				(ch[ni2].y - ch[i2].y) * (ch[ni1].x - ch[i1].x))
				i1 = ni1;
			else i2 = ni2;
		}
	}
	return res;
}

int main() {
	int n;
	vector<point> p;
	scanf("%d", &n);
	for(int i=0,x,y; i<n; i++) {
		scanf("%d%d", &x, &y);
		p.push_back(point(x, y));
	}
	double lo = 0, hi = 1e9;
	for(int tt=0; tt<100; tt++) {
		double mid = (lo + hi) / 2;
		vector<Line> ln;
		for(int i=0; i<n; i++) {
			double dx = -(p[(i+1)%n].y - p[i].y);
			double dy = p[(i+1)%n].x - p[i].x;
			double sz = hypot(dx, dy);
			dx = dx / sz * mid, dy = dy / sz * mid;
			ln.push_back(Line(point(p[i].x + dx, p[i].y + dy), 
				point(p[(i+1)%n].x + dx, p[(i+1)%n].y + dy)));
		}
		vector<point> ch = HPI(ln);
		if(ch.size() >= 3) {
			double d = calipers(ch);
			if(d >= mid * 2) lo = mid;
			else hi = mid;
		} else hi = mid;
	}
	printf("%.3f", lo);
	return 0;
}

Compilation message

twocircles.cpp:33:10: error: 'line' was not declared in this scope
 bool bad(line& a, line& b, line& c) {
          ^~~~
twocircles.cpp:33:10: note: suggested alternative: 'Line'
 bool bad(line& a, line& b, line& c) {
          ^~~~
          Line
twocircles.cpp:33:16: error: 'a' was not declared in this scope
 bool bad(line& a, line& b, line& c) {
                ^
twocircles.cpp:33:19: error: 'line' was not declared in this scope
 bool bad(line& a, line& b, line& c) {
                   ^~~~
twocircles.cpp:33:19: note: suggested alternative: 'Line'
 bool bad(line& a, line& b, line& c) {
                   ^~~~
                   Line
twocircles.cpp:33:25: error: 'b' was not declared in this scope
 bool bad(line& a, line& b, line& c) {
                         ^
twocircles.cpp:33:28: error: 'line' was not declared in this scope
 bool bad(line& a, line& b, line& c) {
                            ^~~~
twocircles.cpp:33:28: note: suggested alternative: 'Line'
 bool bad(line& a, line& b, line& c) {
                            ^~~~
                            Line
twocircles.cpp:33:34: error: 'c' was not declared in this scope
 bool bad(line& a, line& b, line& c) {
                                  ^
twocircles.cpp:33:35: error: expression list treated as compound expression in initializer [-fpermissive]
 bool bad(line& a, line& b, line& c) {
                                   ^
twocircles.cpp:40:26: error: 'line' was not declared in this scope
 vector<point> HPI(vector<line>& ln) {
                          ^~~~
twocircles.cpp:40:26: note: suggested alternative: 'Line'
 vector<point> HPI(vector<line>& ln) {
                          ^~~~
                          Line
twocircles.cpp:40:30: error: template argument 1 is invalid
 vector<point> HPI(vector<line>& ln) {
                              ^
twocircles.cpp:40:30: error: template argument 2 is invalid
twocircles.cpp: In function 'std::vector<point> HPI(int&)':
twocircles.cpp:41:8: error: 'line' was not declared in this scope
  deque<line> dq;
        ^~~~
twocircles.cpp:41:8: note: suggested alternative: 'Line'
  deque<line> dq;
        ^~~~
        Line
twocircles.cpp:41:12: error: template argument 1 is invalid
  deque<line> dq;
            ^
twocircles.cpp:41:12: error: template argument 2 is invalid
twocircles.cpp:2:23: error: request for member 'size' in 'ln', which is of non-class type 'int'
 #define SZ(x) ((int)x.size())
                       ^
twocircles.cpp:42:17: note: in expansion of macro 'SZ'
  for(int i=0; i<SZ(ln); i++) {
                 ^~
twocircles.cpp:43:12: error: request for member 'size' in 'dq', which is of non-class type 'int'
   while(dq.size() >= 2 && bad(dq[dq.size()-2], dq.back(), ln[i]))
            ^~~~
twocircles.cpp:43:37: error: request for member 'size' in 'dq', which is of non-class type 'int'
   while(dq.size() >= 2 && bad(dq[dq.size()-2], dq.back(), ln[i]))
                                     ^~~~
twocircles.cpp:43:51: error: request for member 'back' in 'dq', which is of non-class type 'int'
   while(dq.size() >= 2 && bad(dq[dq.size()-2], dq.back(), ln[i]))
                                                   ^~~~
twocircles.cpp:43:63: error: invalid types 'int[int]' for array subscript
   while(dq.size() >= 2 && bad(dq[dq.size()-2], dq.back(), ln[i]))
                                                               ^
twocircles.cpp:43:64: error: 'bad' cannot be used as a function
   while(dq.size() >= 2 && bad(dq[dq.size()-2], dq.back(), ln[i]))
                                                                ^
twocircles.cpp:44:7: error: request for member 'pop_back' in 'dq', which is of non-class type 'int'
    dq.pop_back();
       ^~~~~~~~
twocircles.cpp:45:12: error: request for member 'size' in 'dq', which is of non-class type 'int'
   while(dq.size() >= 2 && bad(dq[0], dq[1], ln[i]))
            ^~~~
twocircles.cpp:45:35: error: invalid types 'int[int]' for array subscript
   while(dq.size() >= 2 && bad(dq[0], dq[1], ln[i]))
                                   ^
twocircles.cpp:45:42: error: invalid types 'int[int]' for array subscript
   while(dq.size() >= 2 && bad(dq[0], dq[1], ln[i]))
                                          ^
twocircles.cpp:45:49: error: invalid types 'int[int]' for array subscript
   while(dq.size() >= 2 && bad(dq[0], dq[1], ln[i]))
                                                 ^
twocircles.cpp:45:50: error: 'bad' cannot be used as a function
   while(dq.size() >= 2 && bad(dq[0], dq[1], ln[i]))
                                                  ^
twocircles.cpp:46:7: error: request for member 'pop_front' in 'dq', which is of non-class type 'int'
    dq.pop_front();
       ^~~~~~~~~
twocircles.cpp:47:9: error: request for member 'size' in 'dq', which is of non-class type 'int'
   if(dq.size() < 2 || !bad(dq.back(), ln[i], dq[0]))
         ^~~~
twocircles.cpp:47:31: error: request for member 'back' in 'dq', which is of non-class type 'int'
   if(dq.size() < 2 || !bad(dq.back(), ln[i], dq[0]))
                               ^~~~
twocircles.cpp:47:43: error: invalid types 'int[int]' for array subscript
   if(dq.size() < 2 || !bad(dq.back(), ln[i], dq[0]))
                                           ^
twocircles.cpp:47:50: error: invalid types 'int[int]' for array subscript
   if(dq.size() < 2 || !bad(dq.back(), ln[i], dq[0]))
                                                  ^
twocircles.cpp:47:51: error: 'bad' cannot be used as a function
   if(dq.size() < 2 || !bad(dq.back(), ln[i], dq[0]))
                                                   ^
twocircles.cpp:48:7: error: request for member 'push_back' in 'dq', which is of non-class type 'int'
    dq.push_back(ln[i]);
       ^~~~~~~~~
twocircles.cpp:48:21: error: invalid types 'int[int]' for array subscript
    dq.push_back(ln[i]);
                     ^
twocircles.cpp:51:8: error: request for member 'size' in 'dq', which is of non-class type 'int'
  if(dq.size() >= 3) for(int i=0; i<sz(dq); i++) {
        ^~~~
twocircles.cpp:51:36: error: 'sz' was not declared in this scope
  if(dq.size() >= 3) for(int i=0; i<sz(dq); i++) {
                                    ^~
twocircles.cpp:54:26: error: invalid types 'int[int]' for array subscript
   if(!line_intersect(dq[i].s, dq[i].t, dq[j].s, dq[j].t, v)) continue;
                          ^
twocircles.cpp:54:35: error: invalid types 'int[int]' for array subscript
   if(!line_intersect(dq[i].s, dq[i].t, dq[j].s, dq[j].t, v)) continue;
                                   ^
twocircles.cpp:54:44: error: invalid types 'int[int]' for array subscript
   if(!line_intersect(dq[i].s, dq[i].t, dq[j].s, dq[j].t, v)) continue;
                                            ^
twocircles.cpp:54:53: error: invalid types 'int[int]' for array subscript
   if(!line_intersect(dq[i].s, dq[i].t, dq[j].s, dq[j].t, v)) continue;
                                                     ^
twocircles.cpp:54:7: error: 'line_intersect' was not declared in this scope
   if(!line_intersect(dq[i].s, dq[i].t, dq[j].s, dq[j].t, v)) continue;
       ^~~~~~~~~~~~~~
twocircles.cpp:54:7: note: suggested alternative: 'getIntersect'
   if(!line_intersect(dq[i].s, dq[i].t, dq[j].s, dq[j].t, v)) continue;
       ^~~~~~~~~~~~~~
       getIntersect
twocircles.cpp: In function 'int main()':
twocircles.cpp:103:28: error: invalid initialization of reference of type 'int&' from expression of type 'std::vector<Line>'
   vector<point> ch = HPI(ln);
                            ^
twocircles.cpp:40:15: note: in passing argument 1 of 'std::vector<point> HPI(int&)'
 vector<point> HPI(vector<line>& ln) {
               ^~~
twocircles.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
twocircles.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~