oj.uz

Submission #363740

# Submission time Handle Problem Language Result Execution time Memory
363740 2021-02-07T07:21:07 Z arnold518 SIR (COI15_sir) C++14
100 / 100
 250 ms 18652 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3e5;

struct Point
{
	ll x, y;
};

Point operator + (Point p, Point q) { return {p.x+q.x, p.y+q.y}; }
Point operator - (Point p, Point q) { return {p.x-q.x, p.y-q.y}; }
ll ccw(Point p, Point q) { return p.x*q.y-p.y*q.x; }
ll dot(Point p, Point q) { return p.x*q.x+p.y*q.y; }

int N, M;
Point A[MAXN+10], B[MAXN+10];
vector<Point> UH, DH, CH;

bool f(Point p, Point q)
{
	Point d=q-p;

	if(ccw(q-p, DH[0]-p)<=0) return false;
	if(ccw(q-p, UH[0]-p)<=0) return false;

	//if(d.x<0 || (d.x==0 && d.y<0)) d.x*=-1, d.y*=-1;
	int lo=-1, hi=DH.size()-1;
	while(lo+1<hi)
	{
		int mid=lo+hi>>1;
		if(ccw(d, DH[mid+1]-DH[mid])>=0) hi=mid;
		else lo=mid;
	}
	if(ccw(q-p, DH[hi]-p)<=0) return false;

	//d.x*=-1, d.y*=-1;
	lo=-1, hi=UH.size()-1;
	while(lo+1<hi)
	{
		int mid=lo+hi>>1;
		if(ccw(d, UH[mid+1]-UH[mid])>=0) hi=mid;
		else lo=mid;
	}
	if(ccw(q-p, UH[hi]-p)<=0) return false;

	return true;
}

ll ans=0, sum[MAXN+10];

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%lld%lld", &A[i].x, &A[i].y);
	scanf("%d", &M);
	for(int i=1; i<=M; i++) scanf("%lld%lld", &B[i].x, &B[i].y);

	sort(B+1, B+M+1, [&](const Point &p, const Point &q)
	{
		if(p.x!=q.x) return p.x<q.x;
		return p.y<q.y;
	});
	for(int i=1; i<=M; i++)
	{
		while(DH.size()>1 && ccw(DH[DH.size()-1]-DH[DH.size()-2], B[i]-DH[DH.size()-2])<=0) DH.pop_back();
		DH.push_back(B[i]);
	}
	reverse(B+1, B+M+1);
	for(int i=1; i<=M; i++)
	{
		while(UH.size()>1 && ccw(UH[UH.size()-1]-UH[UH.size()-2], B[i]-UH[UH.size()-2])<=0) UH.pop_back();
		UH.push_back(B[i]);
	}
	for(int i=0; i<DH.size(); i++) CH.push_back(DH[i]);
	for(int i=1; i+1<UH.size(); i++) CH.push_back(UH[i]);

	for(int i=2; i<=N; i++)
	{
		sum[i]=sum[i-1]+ccw(A[i-1], A[i]);
	}
	
	for(int i=1, j=2; i<=N; i++)
	{
		for(; i==j || f(A[i], A[j]); j=(j==N ? 1 : j+1));
		int t=j-1;
		if(t==0) t=N;

		ll val=0;
		if(i<=t)
		{
			val+=sum[t]-sum[i];
		}
		else
		{
			val+=sum[N]-sum[i]+sum[t]+ccw(A[N], A[1]);
		}
		val+=ccw(A[t], A[i]);
		val=abs(val);
		ans=max(ans, val);
	}
	printf("%lld\n", ans);
}

Compilation message

sir.cpp: In function 'bool f(Point, Point)':
sir.cpp:35:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |   int mid=lo+hi>>1;
      |           ~~^~~
sir.cpp:45:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |   int mid=lo+hi>>1;
      |           ~~^~~
sir.cpp: In function 'int main()':
sir.cpp:79:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for(int i=0; i<DH.size(); i++) CH.push_back(DH[i]);
      |               ~^~~~~~~~~~
sir.cpp:80:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for(int i=1; i+1<UH.size(); i++) CH.push_back(UH[i]);
      |               ~~~^~~~~~~~~~
sir.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
sir.cpp:59:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |  for(int i=1; i<=N; i++) scanf("%lld%lld", &A[i].x, &A[i].y);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sir.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |  scanf("%d", &M);
      |  ~~~~~^~~~~~~~~~
sir.cpp:61:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |  for(int i=1; i<=M; i++) scanf("%lld%lld", &B[i].x, &B[i].y);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 508 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 2 ms 492 KB Output is correct

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 12452 KB Output is correct
2 Correct 222 ms 10936 KB Output is correct
3 Correct 196 ms 13020 KB Output is correct
4 Correct 53 ms 3948 KB Output is correct
5 Correct 167 ms 18652 KB Output is correct
6 Correct 157 ms 16108 KB Output is correct