Submission #363736

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
363736	2021-02-07T07:03:00 Z	arnold518	SIR (COI15_sir)	C++14	51 / 100	1000 ms	11616 KB

sir

#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;

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=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;
		for(int k=i; k!=t; k=(k==N ? 1 : k+1))
		{
			val+=ccw(A[k], A[(k==N ? 1 : k+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	364 KB	Output is correct
2	Correct	3 ms	364 KB	Output is correct
3	Correct	16 ms	492 KB	Output is correct
4	Correct	8 ms	364 KB	Output is correct
5	Correct	3 ms	492 KB	Output is correct
6	Correct	9 ms	364 KB	Output is correct

Subtask #3

0 / 49.0

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