oj.uz

Submission #363737

# Submission time Handle Problem Language Result Execution time Memory
363737 2021-02-07T07:05:43 Z arnold518 SIR (COI15_sir) C++14
51 / 100
 1000 ms 12508 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)
{
	for(int i=0; i<CH.size(); i++)
	{
		if(ccw(q-p, CH[i]-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);
		//printf("%d %d : %lld\n", i, t, val);
		ans=max(ans, val);
	}
	printf("%lld\n", ans);
}

Compilation message

sir.cpp: In function 'bool f(Point, Point)':
sir.cpp:26:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(int i=0; i<CH.size(); i++)
      |               ~^~~~~~~~~~
sir.cpp: In function 'int main()':
sir.cpp:58:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i=0; i<DH.size(); i++) CH.push_back(DH[i]);
      |               ~^~~~~~~~~~
sir.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(int i=1; i+1<UH.size(); i++) CH.push_back(UH[i]);
      |               ~~~^~~~~~~~~~
sir.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
sir.cpp:38:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |  for(int i=1; i<=N; i++) scanf("%lld%lld", &A[i].x, &A[i].y);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sir.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |  scanf("%d", &M);
      |  ~~~~~^~~~~~~~~~
sir.cpp:40:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |  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 364 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 5 ms 492 KB Output is correct
2 Correct 4 ms 364 KB Output is correct
3 Correct 12 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 4 ms 492 KB Output is correct
6 Correct 2 ms 492 KB Output is correct

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 12508 KB Time limit exceeded
2 Halted 0 ms 0 KB -