Submission #21034

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
21034	2017-03-30T08:16:38 Z	gs14004	SIR (COI15_sir)	C++11	100 / 100	299 ms	12752 KB

sir

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int offset = 200002;

int n, m;
pi a[600005];

lint ccw(pi a, pi b, pi c){
	int dx1 = b.first - a.first;
	int dy1 = b.second - a.second;
	int dx2 = c.first - a.first;
	int dy2 = c.second - a.second;
	return 1ll * dx1 * dy2 - 1ll * dy1 * dx2;
}

lint dist(pi a, pi b){
	return 1ll * (b.first - a.first) * (b.first - a.first) + 1ll * (b.second - a.second) * (b.second - a.second);
}

vector<pi> h1, h2;

void get_hull(){
	pi b[300005];
	scanf("%d",&m);
	for(int i=0; i<m; i++){
		scanf("%d %d",&b[i].first, &b[i].second);
	}
	sort(b, b+m);
	for(int i=0; i<m; i++){
		while(h1.size() >= 2 && ccw(h1[h1.size()-2], h1.back(), b[i]) >= 0){
			h1.pop_back();
		}
		while(h2.size() >= 2 && ccw(h2[h2.size()-2], h2.back(), b[i]) <= 0){
			h2.pop_back();
		}
		h1.push_back(b[i]);
		h2.push_back(b[i]);
	}
}

bool has_ccwr(pi s, pi e){ 
	if(s == e) return 0; 
	if(s.first == e.first){
		if(ccw(s, e, h1.front()) <= 0) return 1;
		if(ccw(s, e, h1.back()) <= 0) return 1;
		return 0;
	}
	if(s.first < e.first){
		int st = 0, ed = h2.size() - 1;
		while(st != ed){
			int m = (st + ed) / 2;
			lint t1 = ccw(s, e, h2[m]);
			lint t2 = ccw(s, e, h2[m+1]);
			if(t1 <= t2){
				ed = m;
			}
			else st = m+1;
		}
		return ccw(s, e, h2[st]) <= 0;
	}
	else{
		int st = 0, ed = h1.size() - 1;
		while(st != ed){
			int m = (st + ed) / 2;
			lint t1 = ccw(s, e, h1[m]);
			lint t2 = ccw(s, e, h1[m+1]);
			if(t1 <= t2){
				ed = m;
			}
			else st = m+1;
		}
		return ccw(s, e, h1[st]) <= 0;
	}
}

int rmax[300005];

int main(){
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		scanf("%d %d",&a[i].first, &a[i].second);
		a[n+i] = a[i];
	}
	get_hull();
	int p = 0;
	for(int i=0; i<n; i++){
		while(!has_ccwr(a[i], a[p])) p++;
		rmax[i] = p - 1;
	}
	int ccap = 0;
	lint ret = 0, cur = 0;
	for(int i=0; i<n; i++){
		while(ccap < rmax[i]){
			cur += ccw(a[i], a[ccap], a[ccap+1]);
			ccap++;
		}
		ret = max(ret, cur);
		cur -= ccw(a[i], a[i+1], a[ccap]);
	}
	printf("%lld",ret);
	// make convex hull
}

Compilation message

sir.cpp: In function 'void get_hull()':
sir.cpp:43:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&m);
                ^
sir.cpp:45:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&b[i].first, &b[i].second);
                                           ^
sir.cpp: In function 'int main()':
sir.cpp:98:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
sir.cpp:100:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a[i].first, &a[i].second);
                                           ^

Subtask #1

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	10104 KB	Output is correct
2	Correct	0 ms	10100 KB	Output is correct
3	Correct	0 ms	10104 KB	Output is correct
4	Correct	0 ms	10100 KB	Output is correct

Subtask #2

39.0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	10104 KB	Output is correct
2	Correct	3 ms	10104 KB	Output is correct
3	Correct	3 ms	10108 KB	Output is correct
4	Correct	3 ms	10104 KB	Output is correct
5	Correct	0 ms	10104 KB	Output is correct
6	Correct	3 ms	10108 KB	Output is correct

Subtask #3

49.0 / 49.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	299 ms	11472 KB	Output is correct
2	Correct	279 ms	10780 KB	Output is correct
3	Correct	253 ms	12752 KB	Output is correct
4	Correct	46 ms	10104 KB	Output is correct
5	Correct	179 ms	11472 KB	Output is correct
6	Correct	203 ms	10108 KB	Output is correct